ブログで書いてほしい内容受付中!! 詳しくはこちら

AtCoder Beginner Contest 131 に参加したよ【Python3】【ABC 131】

ABC131に参加したよ

スンマセン、今回 D まで解いたあと疲れてて寝てしまいました。。。E以降はできそうな気もするので後日チャレンジしてみます。

サトゥー

一応レートは上がったよ、1週間くらい競プロできてなかったけどよかった
・ABC 131 に参加したので記録だよ ・例のごとく Python で書いていくよ ・途中で疲労が限界に達して寝てしまったけど4完したよ

ABC131 A – Security

すぬけ君の管理する研究室の扉にはロックがかかっており、解錠にはセキュリティコードを入力する必要があります。
セキュリティコードは \(4\) 桁の数字列です。セキュリティコードが「入力しづらい」とは、同じ数字が連続する箇所が存在することを言います。
現在のセキュリティコード \(S\) が与えられます。\(S\) が「入力しづらい」なら "Bad" を、そうでなければ "Good" を出力してください。

https://atcoder.jp/contests/abc131/tasks/abc131_a

S[0] == S[1] or S[1] == S[2] or S[2] == S[3] のときは "Bad" 、それ以外は "Good" と出力すればいいですね。

回答案

以下のコードで Python3 で 17 ms で AC。

s = input()
if s[0] == s[1] or s[1] == s[2] or s[2] == s[3]:
	print("Bad")
else:
	print("Good")

ABC131 B – Bite Eating

\(N\) 個のリンゴがあります。これらはそれぞれリンゴ \(1\) 、リンゴ \(2\) 、リンゴ \(3\) 、…、リンゴ \(N\) と呼ばれており、リンゴ \(i\) の「味」は \(L + i – 1\) です。「味」は負になることもありえます。
また、\(1\) 個以上のリンゴを材料として、アップルパイをつくることができます。その「味」は、材料となったリンゴの「味」の総和となります。
あなたはこれらのリンゴを全て材料として、アップルパイをつくる予定でしたが、おなかがすいたので \(1\) 個だけ食べることにしました。勿論、食べてしまったリンゴはアップルパイの材料にはできません。
つくる予定だったアップルパイとできるだけ同じものをつくりたいので、\(N\) 個のリンゴ全てを材料としてできるアップルパイの「味」と、食べていない \(N − 1\) 個のリンゴを材料としてできるアップルパイの「味」の差の絶対値ができるだけ小さくなるように、食べるリンゴを選ぶことにしました。
このようにして選ばれたリンゴを食べた時、食べていない \(N − 1\) 個のリンゴを材料としてできるアップルパイの「味」を求めてください。
なお、この値は一意に定まることが証明できます。

https://atcoder.jp/contests/abc131/tasks/abc131_b

なぜかこの問題に苦戦した。。。

普通に最も味の絶対値が小さいやつを除けば終わりですね。

回答案

自分はコンテスト中には以下の3パターンに場合分けして求めました。 Python3 で 20 ms で AC。

N, L = map(int, input().split())
a = N * (L - 1) + N * (N + 1) // 2
if L > 0:
	print(a - L)
elif L + N - 1 < 0:
	print(a - (L + N - 1))
else:
	print(a)

ABC131 C – Anti-Division

整数 \(A,B,C,D\) が与えられます。\(A\) 以上 \(B\) 以下の整数のうち、\(C\) でも \(D\) でも割り切れないものの個数を求めてください。

https://atcoder.jp/contests/abc131/tasks/abc131_c

これは数学的には非常に典型的なやつですね。

\(1\) から \(N\) までの整数のうち、 \(K\) の倍数の個数は \( \lfloor \frac{N}{K} \rfloor \) 個になります。

これを応用して、包除原理的に考えると \(K\) または \(L\) の倍数の個数は \( \lfloor \frac{N}{K} \rfloor \) + \( \lfloor \frac{N}{L} \rfloor \) – \( \lfloor \frac{N}{lcm(K, L)} \rfloor \) になりますね。

ということで、2数の最小公倍数を求める必要がありますね。最小公倍数の求め方については以下で触れました。

Python3 でN個の数の最小公倍数・最大公約数を求めたいとき【AtCoder】

今回は \(A\) 以上 \(B\) 以下の整数という範囲指定があるので、「 \(B\) 以下の条件を満たす個数」 – 「 \(A – 1\) 以下の条件を満たす個数」とうまく言い換えることによって解決してあげましょう。

回答案

以下のコードで Python3 で 35 ms で AC。

from fractions import gcd

A, B, C, D = map(int, input().split())
l = C * D // gcd(C, D)
x = (A - 1) - (A - 1) // C - (A - 1) // D + (A - 1) // l
y = B - B // C - B // D + B // l
print(y - x)

ABC131 D – Megalomania

AtCoder 王国の王立問題工房で ABC 管理官の座に就いたキザハシ君は、浮かれるあまり仕事を引き受けすぎてしまいました。
現在の時刻は \(0\) です。キザハシ君は \(1\) から \(N\) までの番号が振られた \(N\) 件の仕事を持っています。
キザハシ君が仕事 \(i\) を終えるには \(A_i\) 単位時間かかります。また、仕事 \(i\) の〆切は時刻 \(B_i\) であり、これまでに仕事を終わらせる必要があります。時刻 \(B_i\)ちょうどに仕事 \(i\) を終わらせてもかまいません。
キザハシ君は \(2\) 件以上の仕事を同時にすることはできませんが、ある仕事を終わらせた直後に別の仕事を始めることはできます。
キザハシ君はすべての仕事を〆切までに終わらせることができるでしょうか。可能ならば "Yes"、不可能ならば "No" を出力してください。

https://atcoder.jp/contests/abc131/tasks/abc131_d

問題文読んだ感じ、締切が早いやつからこなしていきたい気持ちがしますよね。(感覚的にそんな気がしませんか)

ということで、\(B_i\) でソートしてあげて、 \(A_i\) までの累積時間が時刻 \(B_i\) を超えてないかをチェックしていけば良さそうですね。

\(B_i\) についてソートするときには当然ながら \(A_i\) もこれにしたがってソートしたいので、便宜上これらを \(X_i\) とまとめてしまいます。

回答案

以下のコードで Python3 では 1181 ms で AC でした。

N = int(input())
X = [list(map(int, input().split())) for _ in range(N)]
X = sorted(X, key = lambda x: x[1])

# a[i]はA[i]まで終わらせるためにかかる累積時間
a = [0] * N
a[0] = X[0][0]
for i in range(1, N):
	a[i] = a[i - 1] + X[i][0]

for j in range(N):
	if a[j] > X[j][1]:
		print("No")
		exit()
print("Yes")

ABC131 E – Friendships

以下の条件を満たす \(N\) 頂点の無向グラフは存在するでしょうか?

・グラフは単純かつ連結である。
・各頂点には \(1, 2, …, N\) の番号が付けられている。
・グラフの辺数を \(M\) としたとき、各辺には \(1, 2, …, M\) の番号が付けられていて、辺 \(i\) は頂点 \(u_i\) と頂点 \(v_i\) をつなぐ長さ \(1\) の辺である。
・最短距離が \(2\) であるような頂点対 \((i, j) (i < j)\) が、ちょうど \(K\) 個存在する。

条件を満たすグラフが存在するならば \(1\) つ構築してください。

https://atcoder.jp/contests/abc131/tasks/abc131_e

まずは言葉の意味を確認しましょう。

  • 無向グラフ = 辺に向きがないグラフ
  • グラフが単純 = 多重辺やループ(同じ頂点を結ぶ辺)が存在しないもの
  • グラフが連結 = 任意の2頂点を結ぶ道が作れる(要するに全部つながってる)

\(N = 5\) の場合で色々と図を書いて試してみたら、次のような規則性がありそうなことが分かりました。

サトゥー

どうやら \(K > {}_{N – 1} C _2\) のときはグラフできないっぽい

で、\(K\) の上限である \(K_0 = {}_{N – 1} C _2\) のときは、画像のようになると。

条件を満たすグラフの例

このとき、頂点 \(1\) 以外の任意の \(2\) 頂点間の距離が \(2\) になることがわかりますね。こういう形のグラフをスターと言うそうです。

で、ここから頂点 \(1\) 以外のある \(2\) 頂点を選ぶと、その頂点間の距離が \(1\) になり、他の距離は変わらないので \(K\) が \(1\) だけ少ないものが構築できますね。

この操作を繰り返せば、残り全ての \(K\) についてのグラフが構築できそうです。実装してみましょう。

回答案

スターを作ったあとの実装に少し時間がかかりました。

以下のコードで Python3 で 24 ms で AC でした。

N, K = map(int, input().split())
K0 = (N - 1) * (N - 2) // 2
if K > K0:
	print(-1)
else:
	print((N - 1) + (K0 - K))  # K0-Kがスターに追加する個数
	# まずは頂点1を中心にしてスターを作る
	for i in range(2, N + 1):
		print(1, i)
	# 追加分を出力
	cnt = 0
	for i in range(2, N):
		for j in range(i + 1, N + 1):
			cnt += 1
			if cnt > K0 - K:
				break
			print(i, j)

サトゥー

いったんここまで。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)