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

AtCoder Beginner Contest の B 問題全部やったので詰まったやつや面白かったやつを紹介する【Python3】

時間を見つけて定期的に AtCoder Beginner Contest の過去問を埋めていたのですが、やっと B が全て終わったので、ここまでの復習がてらまとめてみます。

A 問題は基本的に詰まることはほぼ無かったけど、B の一部の問題については知識的な穴がチラホラあったので、そのへんを。

・AtCoder ABC の B まで全部解いたよ ・詰まったところをいくつか紹介しているよ ・完全に個人的なメモだよ

ABC 027 B – 島と橋

\(N\) 個の島が横一列に並んでいる。 \(1 \leq i \leq N−1\) について、左から \(i\) 番目の島と \(i+1\) 番目の島は隣り合っている。
はじめ、左から \(i (1 \leq i \leq N)\) 番目の島には \(a_i\) 人の住人が住んでいる。 高橋君はすべての島に同じ人数の住人が住むようにしたいと考えている。
高橋君は隣り合う \(2\) つの島の間に橋を架けることができる。 また、直接的または間接的に橋で結ばれた複数の島の間で、住人を自由に移動させることができる。
すべての島に同じ人数の住人が住むようにするために、架ける必要のある橋の本数の最小値を求めよ。

https://atcoder.jp/contests/abc027/tasks/abc027_b

なぜかこの問題、最後まで悩んでいた。。。苦手意識でもあるのだろうか、考え方から全然思いつかなくて苦戦しました。

まず、 sum(a) が N で割り切れない場合は「すべての島に同じ人数の住人が住む」状態は実現できないので不可能になります。

あとは \(N – 1\) 個のそれぞれの島と島の間について、それぞれの島に住む人数は n = sum(a) // N 人ですから、

発想

橋が必要かどうか?
→その橋を通る人がいるかどうか?
→橋の片側について、必要な人数(島数 × n )とちょうど同じ人数がいるか?

という発想ができればあとはカンタン。

自分の回答

N = int(input())
*a, = map(int, input().split())

if sum(a) % N != 0:
	print(-1)
	exit()

n = sum(a) // N
ans = 0
for i in range(N - 1):
	if sum(a[: i + 1]) != n * (i + 1):
		ans += 1
print(ans)

ABC 045 B – Card Game for Three (ABC Edit)

A さん、B さん、C さんの \(3\) 人が以下のようなカードゲームをプレイしています。

・最初、\(3\) 人はそれぞれ "a""b""c" いずれかの文字が書かれたカードを、何枚か持っている。これらは入力で与えられた順番に持っており、途中で並べ替えたりしない。

・ A さんのターンから始まる。

・現在自分のターンである人がカードを \(1\) 枚以上持っているならば、そのうち先頭のカードを捨てる。その後、捨てられたカードに書かれているアルファベットと同じ名前の人 (例えば、カードに "a" と書かれていたならば A さん) のターンとなる。

・現在自分のターンである人がカードを \(1\) 枚も持っていないならば、その人がゲームの勝者となり、ゲームは終了する。

\(3\) 人が最初に持っているカードがそれぞれ先頭から順に与えられます。 具体的には、文字列 \(S_A\)、\(S_B\)、\(S_C\) が与えられます。文字列 \(S_A\) の \(i\) 文字目 \(( 1 \leq i \leq |S_A|\) ) に書かれている文字が、A さんの持っている中で先頭から \(i\) 番目のカードに 書かれている文字です。文字列 \(S_B\)、 \(S_C\) についても同様です。
最終的に誰がこのゲームの勝者となるかを求めてください。

https://atcoder.jp/contests/abc045/tasks/abc045_b

ルール自体は簡単で、実装も愚直にやればできるんだけど、簡潔にコードを書くすべが見つからなかったのでマジで愚直に書きました。

自分の回答

こんな感じ。

S = [input() for _ in range(3)]
now = 0
count = len(S[0]) + len(S[1]) + len(S[2])
for _ in range(count):
	if len(S[now]) == 0:
		if now == 0:
			print("A")
		elif now == 1:
			print("B")
		else:
			print("C")
		exit()
	else:
		if S[now][0] == "a":
			if now == 0:
				S[0] = S[0][1:]
			elif now == 1:
				S[1] = S[1][1:]
			else:
				S[2] = S[2][1:]
			now = 0
		elif S[now][0] == "b":
			if now == 0:
				S[0] = S[0][1:]
			elif now == 1:
				S[1] = S[1][1:]
			else:
				S[2] = S[2][1:]
			now = 1
		else:
			if now == 0:
				S[0] = S[0][1:]
			elif now == 1:
				S[1] = S[1][1:]
			else:
				S[2] = S[2][1:]
			now = 2

サトゥー

うーん、なんか同じ処理がたくさんあるし、これはもっとシンプルに実装できそう

シンプルに書くためのアイデア

なんかないかなぁ〜と人の解答をみてたら、こんなアイデアで書いているものがあったのでシェア。

参考 提出 #4130525AtCoder
s={i:list(input()) for i in "abc"}
x="a"
while s[x]:
    x=s[x].pop(0)
print(x.upper())

え、5行で終わってるやん…

せっかくなので丁寧に読んでみます。

s = {i: list(input()) for i in "abc"}

s は input() をリスト化したもので、後半の工夫から s[a], s[b], s[c] という風に定められます。ココがもうスマート。

x = "a"
while s[x]:
    x = s[x].pop(0)

はじめに、 s の添字 x に a を代入しておきます。

while s[x] というのは、おそらく「リスト s[x] 内に要素がある限り」っていうことなんでしょうかね、調べてもいまいち分からなかった。

x = s[x].pop(0) で s[x] の最初の要素を削除し、その値を x に代入していますね。

print(x.upper())

リスト s[x] に要素がなくなったら、x が大文字に変換されて出力されます。

サトゥー

天才ですね

ABC 048 B – Between a and b

非負の整数 \(a, b\) \((a \leq b)\) と、正の整数 \(x\) が与えられます。 \(a\) 以上 \(b\) 以下の整数のうち、\(x\) で割り切れるものの個数を求めてください。

https://atcoder.jp/contests/abc048/tasks/abc048_b

数学って感じの問題。数学のネタとしては超典型的な手法で、集合の差分を求めれば答えが得られます。

自分の回答

a, b, x = map(int, input().split())
print(b // x - (a - 1) // x)
  • b // x は 1 から b までに x でわりきれるものがいくつ出現するか
  • (a - 1) // x は 1 から a – 1 までに x でわりきれるものがいくつ出現するか

なので、これらの差を取ればよいわけです。

サトゥー

なにも考察をせずに素直に x を 1 ずつずらして調べたので死にました。

数学的な考察によって見方をかえることで、うまく計算量を削減して簡単にかんがえることができる、というのを実感しました。(競プロにおいてはめちゃくちゃ重要な考え方っぽい)

ABC 060 B – Choose Integers

あなたは、正の整数をいくつか選び、それらの総和を求めます。
選ぶ数の上限や、選ぶ整数の個数に制限はありません。 どんなに大きな整数を選んでもよいですし、整数を \(5000\) 兆個選んでもよいです。 ただし、選ぶ数はすべて \(A\) の倍数でなくてはいけません。 また、少なくとも \(1\) つは整数を選ばなくてはいけません。
そして総和を \(B\) で割ったあまりが \(C\) となるようにしたいです。 こうなるように整数を選ぶことが出来るか判定してください。
出来るならば "YES"、そうでないならば "NO" を出力してください。

https://atcoder.jp/contests/abc060/tasks/abc060_b

これ、解いた当時は実験してみて、なんとなーくこんな性質ありそうだな〜で書いたら AC だったのよね。(高校の数学覚えてなかった普通に)

自分の回答

from fractions import gcd
A, B, C = map(int, input().split())
if C % gcd(A, B) == 0:
	print("YES")
else:
	print("NO")

二元一次の不定方程式の話

なんでこうなるんだろうって考えてたら、背景に二元一次の不定方程式があるんですね。Bezout の定理みたいなの無かったっけ?

A の倍数を x 個選ぶとして、その総和を B でわった商を y とするならば、
A * x = B * y + C
=> A * x + B * (-y) = C

なるほど、二元の一次の不定方程式なら重要な性質がありますね。

「 \(ax + by = c\) が整数解をもつこと」と「 \(c\) は \(gcd(a, b)\) の倍数であること」は同値

応用編として難関大の入試で証明問題が出がちなやつがこれですね。↓

「 \(ax + by = 1\) が整数解を持つこと」と「 \(a\) と \(b\) は互いに素であること」は同値

ABC 107 B – Grid Compression

縦 \(H\) 行、横 \(W\) 列のマス目があります。 上から \(i\) 行目、左から \(j\) 列目のマスを \((i,j)\) と表します。 各マスは白または黒です。 マス目の配色は、\(H\) 行 \(W\) 列の行列 \((a_{i,j})\) によって与えられます。 \(a_{i,j}\) が "." ならばマス \((i,j)\) は白であり、\(a_{i,j}\) が "#" ならばマス \((i,j)\) は黒です。
すぬけ君はこのマス目を圧縮しようとしています。 そのために、白いマスのみからなる行または列が存在する間、次の操作を繰り返し行います。
操作: 白いマスのみからなる行または列をひとつ任意に選び、その行または列を取り除いて空白を詰める。
各操作でどの行または列を選ぶかによらず、最終的なマス目は一意に定まることが示せます。 最終的なマス目を求めてください。

https://atcoder.jp/contests/abc107/tasks/abc107_b

普通に転置のうまい方法が知識的に分からなかったので調べて回答しました。

自分の回答

H, W = map(int, input().split())
a = [list(input()) for _ in range(H)]

a = list(zip(*[i for i in a if "#" in i]))
a = list(zip(*[j for j in a if "#" in j]))

for n in range(len(a)):
	print("".join(a[n]))

二次元配列の転置(行と列の入れ替え)

Python では zip() 関数を用いることで簡単に二次元配列の転置ができます。

l = [[1, 2, 3], [4, 5, 6]]

という2行3列の配列があったとき、次のように操作することで行と列を入れ替えることができます。

l_t = [list(i) for i in zip(*l)]
print(l_t)
>>>  [[1, 4], [2, 5], [3, 6]]

今後の予定

今後しばらくは ABC – C をメインでやりつつ、 AGC / ARC あたりの簡単そうな問題を解いていく予定です。平日忙しく、思ったように時間をかけられてませんが、暇な時間を見つけてはちょくちょくこなして進捗を生んでいきたいです。

またキリのいいところで記事にして復習しますね。

サトゥー

早く緑になりたい〜〜。。。

コメントを残す

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

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