AtCoder Beginners Contest 302 (ABC302) をPythonで解きました。
見やすいコードを書く練習も兼ねてます。
A - Attack
問題ページ
difficulty: 24
入力
$A$: 敵の体力
$B$: 1回の攻撃で削れる体力
考察
小数点切り上げの割り算が $(A+B-1)//B$ なのを知ってたらすぐに解けます。
A, B = map(int, input().split())
ans = (A + B - 1) // B
print(ans)
$A//B$ で小数点以下切り捨ての割り算をしてみて、
もし$A÷B$の余りが0より大きいときに、答えに1を足すようにしてもACできます。
A, B = map(int, input().split())
ans = A // B
if A % B > 0:
ans += 1
print(ans)
B - Find snuke
問題ページ
difficulty: 352
入力
$H$: 縦の長さ
$W$: 横の長さ
$S_{i,j}$: $i$行目$j$列目に書いてある文字
考察
8方向のベクトルを事前に用意します。
各点について8方向を見て、"snuke"になってたら答えを出力します。
枠外を見に行くとエラーになるので気をつけましょう。
コード
H, W = map(int, input().split())
S = [input() for _ in range(H)]
# 縦・横・斜めの8方向のベクトルをvecsに入れる。
vecs = []
for vi in [-1, 0, 1]:
for vj in [-1, 0, 1]:
if (vi, vj) != (0, 0):
vecs.append((vi, vj))
# 点(i, j)について考える。
for i in range(H):
for j in range(W):
# 点(i, j)から8方向を見て、もしsnukeになってたら答えを出力する。
for vi, vj in vecs:
# H * W の枠外に出てしまうものを除外する。
gi, gj = i + vi * 4, j + vj * 4
if not (0 <= gi < H and 0 <= gj < W):
continue
now_str = ''
ans_list = []
for k in range(5):
ni, nj = i + vi * k, j + vj * k
now_str = now_str + S[ni][nj]
ans_list.append((ni + 1, nj + 1)) # 答えは1-indexedで出力する。
if now_str == 'snuke':
for ans in ans_list:
print(*ans)
C - Almost Equal
問題ページ
difficulty: 469
入力
$N$: 入力される文字列の個数
$M$: 文字列の長さ
$S_i$: $i$個目の文字列
考察
「順列全探索」と呼ばれるタイプの問題です。
$N$も$M$もめちゃくちゃに小さいから、並び替えたのを全通り試してみます。
itertoolの中にあるpermutationsを使うと簡単でオススメです！
2つの文字列を比較するところは、for文の中でコードを書いてもいいんですが、分けて関数にしておくとコードも思考もすっきりしがちです！
コード
from itertools import permutations
# 文字列s1を何文字変更したらs2にできるかを返す関数。
def dist(s1, s2):
different_cnt = 0
for el1, el2 in zip(s1, s2):
if el1 != el2:
different_cnt += 1
return different_cnt
N, M = map(int, input().split())
S = [input() for _ in range(N)]
ans = 'No'
for perm in permutations(range(N)):
is_ok = True
P = []
for idx in perm:
P.append(S[idx])
for i in range(N - 1):
if dist(P[i], P[i + 1]) > 1:
is_ok = False
if is_ok:
ans = 'Yes'
print(ans)
D - Impartial Gift
問題ページ
difficulty: 682
入力
$N$: 青木くんへの贈り物の個数
$M$: すぬけくんへの贈り物の個数
$D$: 2人への贈り物の価値の差を$D$以下にしたい。
$A_i$: $i$個目の青木くんへの贈り物の価値
$B_i$: $i$個目のすぬけくんへの贈り物の価値
考察
「貪欲法」と呼ばれるタイプの解き方をします。
あらかじめ、$A$と$B$をそれぞれ昇順にソートします。
$(P)$
$A$と$B$の中からそれぞれ最大値$a$と$b$を引っ張ってきます。
もし$|a-b|\leq D$ なら、この2つの贈り物は条件を満たしているし、$A$と$B$それぞれの最大値が$a$と$b$なので、これが答えです。
$|a-b|\gt D$ のとき、仮に$a$の方が大きいとします。思い返すと$b$は$B$の中で最も大きな値だったので、もう$B$の中には$a$との差の絶対値が$D$以下になる要素がありません。
つまり、この$a$をつかった贈り物のペアはつくれないことになります。
なので、$a$は捨ててしまって、残った$A$をつかって$(P)$からまた同じ処理をします。
$a$より$b$の方が大きかった場合も同じです。
コード
N, M, D = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort()
ans = -1
# A,Bからそれぞれ最大値を取って来て、差がD以下ならそれが答えになる。(貪欲法)
while len(A) > 0 and len(B) > 0:
a = A.pop()
b = B.pop()
if abs(a - b) <= D:
ans = a + b
break
# aとbで大きい方は、差がD以下になるような選び方ができない。
# ⇒ 大きい方を捨てて、小さい方は元に戻す。
if a < b:
A.append(a)
else:
B.append(b)
print(ans)
E - Isolation
問題ページ
difficulty: 982
入力
$N$: 頂点の数
$Q$: とんでくるクエリの数
クエリ1
頂点$u$と頂点$v$を辺で結ぶ。このクエリの直前は頂点$u$と頂点$v$が辺で結ばれていない。
クエリ2
頂点$v$から出ている辺をすべて削除する(頂点$v$自体は削除しない)。
考察
$S_u$: 頂点$u$と辺で結ばれてる頂点を入れたset
になるリスト$S$を用意します。
クエリ1で頂点$u$と頂点$v$を結ぶときは、$S_u$に$v$を、$S_v$に$u$を追加します。
クエリ2で頂点$v$から出ている辺を削除するときは、$S_v$の中の頂点それぞれについて、その頂点を$u$としたとき$S_u$から$v$を削除します。その処理をすべて終えた後、$S_v$を空のsetにします。
最初はどの頂点も孤立してるから、変数$ans$を$N$にしておきます。
そこから各クエリを処理していきます。
今まで空のsetだったところに要素を追加したときや、要素が入っていたsetが空になったときに、$ans$を$1$増やしたり減らしたりします。
コード
N, Q = map(int, input().split())
S = [set() for _ in range(N)]
ans = N
for _ in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
u, v = query[1] - 1, query[2] - 1
if len(S[u]) == 0:
ans -= 1
S[u].add(v)
if len(S[v]) == 0:
ans -= 1
S[v].add(u)
elif query[0] == 2:
v = query[1] - 1
for u in S[v]:
S[u].discard(v)
if len(S[u]) == 0:
ans += 1
if len(S[v]) > 0:
ans += 1
S[v] = set()
print(ans)