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)