【Atcoder解法検討】ABC302 A~E Python

A - Attack

問題ページ : A - Attack

考察

AをBで割った結果の切り上げ。
切り上げは$(A-1)\ //\ B\ +\ 1$もしくは$(A+B-1)\ //\ B$で求める。

コード

A, B = map(int, input().split())
print((A-1) // B + 1)

B - Find snuke

問題ページ : B - Find snuke

考察

計算量的には余裕があり、バグらないように実装する。
$H \times W$の全マスを起点として全探索。起点から8方向それぞれに5文字分、文字と座標を取り込みます。取り込んだ文字列が"snuke"に一致すれば座標出力。
8方向は移動方向の差分をリストでもっておいてループにとりこむ。
また探索範囲は全マスにしておいて枠外に出る場合はbreakで制限をかけるのが楽。

コード

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

ns = list("snuke")
rs = list(reversed(ns))

dr = [(0,-1), (0,1), (1,-1), (1,0), (1,1), (-1,-1), (-1,0), (-1,1)]
for i in range(H):
    for j in range(W):
        for di, dj in dr:
            tmp1 = []
            tmp2 = []
            for k in range(5):
                ni = i + k * di
                nj = j + k * dj
                if not (0 <= ni < H and 0 <= nj < W):break
                tmp1.append(M[ni][nj])
                tmp2.append((ni+1, nj+1))

            if tmp1 == ns:
                for e in tmp2:
                    print(*e)
                exit()

C - Almost Equal

問題ページ : C - Almost Equal

考察

$N \leq 8$なので順列を全探索しても計算量的には問題ない。
itertools.permutationsを使用して順列の全探索。

コード

from itertools import permutations

N, M = map(int, input().split())
S = [input() for _ in range(N)]
P = list(permutations(S))

for p in P:
    is_Yes = True
    for i in range(N-1):
        first = p[i]
        second = p[i+1]
        
        num = 0
        for j in range(M):
            if first[j] != second[j]:
                num += 1
        if num != 1:
            is_Yes = False
            break
    
    if is_Yes:
        print("Yes")
        exit()

print("No")

D - Impartial Gift

問題ページ : D - Impartial Gift

考察

全探索すると$O(MN)$になりTLE。
Aの選択肢によってBの最適選択肢が決定もしくは限定できる場合にbisect（二分探索）を用いるのはある意味典型。

コード

from bisect import bisect_right

N, M, D = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
B.sort()

ans = -1

for a in A:
    target_price = a + D
    idx = bisect_right(B, target_price)
    if idx == 0:continue
    b = B[idx-1]
    if abs(a-b) <= D:
        ans = max(ans, a + b)

print(ans)

E - Isolation

問題ページ : E - Isolation

考察

query系の問題はどのようなデータ構造を持つかで対処する場合が多いように思う。
本問題は隣接リストのみを管理することで解は得られるがTLEするケースに遭遇する。
TLEとなる要因は
①隣接リストからの削除が$O(N)$となり得るのでクエリ回数をかけて$O(NQ)$
②孤立している頂点の探索が$O(N)$なのでクエリ回数をかけて$O(NQ)$
これらを解消するために
①隣接リストをlistではなくsetで持つ（setの要素削除は$O(1)$）
②孤立している頂点をsetでもち都度追加・削除をおこないながら要素数を出力（setの追加、削除、要素数カウントはいづれも$O(1)$）

コード

N, q = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(q)]

iso = set(range(N))
G = [set() for _ in range(N)]

for com in Q:
    if com[0] == 1:
        u = com[1] - 1
        v = com[2] - 1
        G[u].add(v)
        G[v].add(u)
        if u in iso:
            iso.remove(u)
        if v in iso:
            iso.remove(v)
        print(len(iso))

    if com[0] == 2:
        u = com[1] - 1
        
        if len(G[u]) == 0:
            print(len(iso))
            continue

        for e in G[u]:
            G[e].remove(u)
            if len(G[e]) == 0:
                iso.add(e)
        
        G[u] = set()
        iso.add(u)

        print(len(iso))

青色diff以上は後日挑戦