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

A - Similar String

問題ページ : A - Similar String

考察

冗長というか美しくはありませんが題意どおり愚直に実装。

コード

N = int(input())
S = input()
T = input()

ans = "Yes"
for i in range(N):
    if S[i] == T[i]:
        continue

    if S[i] == "l" and T[i] == "1":
        continue
    if S[i] == "1" and T[i] == "l":
        continue

    if S[i] == "0" and T[i] == "o":
        continue
    if S[i] == "o" and T[i] == "0":
        continue

    ans = "No"

print(ans)

B - Discord

問題ページ : B - Discord

考察

グラフの隣接行列のように、
$$G[i][j] : iとJが隣り合うことがあれば1、なければ0$$という二次元リストを用意し、与えられた各$a_{i,1} ～\ a_{i,N}$からリストを埋めます。
リストを埋め終わったあと、Gから隣り合うことがある組み合わせの数をかぞえ、全組合せ数から引きます。

コード

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

G = [[0] * N for _ in range(N)]

for i in range(M):
    for j in range(N-1):
        a = A[i][j] - 1
        b = A[i][j+1] - 1
        G[a][b] = 1
        G[b][a] = 1

num = 0
for i in range(N):
    for j in range(i+1, N):
        num += G[i][j]

ans = N * (N-1) // 2 - num
print(ans)

C - Dash

問題ページ : C - Dash

考察

体力回復アイテムのある座標$(x_i, y_i)$を$set$でもって、現座標が体力回復アイテムのある座標に一致するか高速かつ低メモリで判定します。
体力回復アイテム取得後は$remove((x_i, y_i))$で$set$から消去することを忘れないように注意します。

コード

N, M, H, K = map(int, input().split())
S = input()
XY =set(tuple(map(int, input().split())) for _ in range(M))
        
dr = dict()
dr["R"] = (1, 0)
dr["L"] = (-1, 0)
dr["U"] = (0, 1)
dr["D"] = (0, -1)

x, y = 0, 0
for i in range(N):
    dx, dy = dr[S[i]]
    x += dx
    y += dy
    
    H -= 1
    if H < 0:
        print("No")
        exit()

    if H < K and (x,y) in XY:
        H = K
        XY.remove((x,y))

print("Yes")

D - Shift vs. CapsLock

問題ページ : D - Shift vs. CapsLock

考察

DPで解きます。
有限回の選択のステップがあり、その選択により最終的な数値が決まり、その数値に関するものを問われる場合（最大値、最小値、ある数値をとりうるか、状態数がいくつになるか、等）は全探索の次にDPを考えて良いと思います。
またDPで解く場合はDPテーブルの定義を明確化することが重要です。明確化できればそれに合わせて機械的にコード化していくイメージです。
今回は
$$ dpa[i] : i文字目をcaps オフの状態で打ったときの最短時間$$$$ dpA[i] : i文字目をcaps オンの状態で打ったときの最短時間$$
としました。

コード

X, Y, Z = map(int, input().split())
S = input()
N = len(S)

# dpa[i] : i文字目をcaps offの状態で打ったときの最短時間
# dpA[i] : i文字目をcaps onの状態で打ったときの最短時間
dpa = [0] * (N+1)
dpA = [0] * (N+1) 
dpA[0] = Z

for i in range(N):
    if S[i] == "a":
        dpa[i+1] = min(dpa[i] + X,      dpA[i] + Z + X)
        dpA[i+1] = min(dpa[i] + Z + Y,  dpA[i] + Y)
    elif S[i] == "A":
        dpa[i+1] = min(dpa[i] + Y,      dpA[i] + Z + Y)
        dpA[i+1] = min(dpa[i] + Z + X,  dpA[i] + X)

print(min(dpa[N], dpA[N]))

E - A Gift From the Stars

問題ページ : E - A Gift From the Stars

考察

ぱっと見は次数に注目すればすぐ解けそうと思いましたがレベル２の星が検出しづらくどのなのかなと。
その後打つ手が思いつかなかったのでとりあえず考えられる例を図示してみました。以下のような感じです。

青が元の星で、塗りつぶした青が各星の根、赤線が手続きにより張った辺になります。
この図の特徴は何かと眺めていると以下の3点に気付きます。
①葉に直接つながっている頂点は星の根
②星の根から距離3にある頂点は星の根
③星の根からの辺が増減することは無い
以上のことから任意の葉を選択しこの葉から各頂点への距離を求め、この距離を3で割って1余る頂点が星の根、星のレベルは根につながる辺の数である。
これで実装できるようになりました。

コード

from collections import deque

N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)

leaf_vertex = -1
for i in range(N):
    if len(G[i]) == 1:
        leaf_vertex = i
        break

dist = [-1] * N
dist[leaf_vertex] = 0
Q = deque()
Q.append(leaf_vertex)
while len(Q) > 0:
    x = Q.popleft()
    for nx in G[x]:
        if dist[nx] != -1: continue
        dist[nx] = dist[x] + 1
        Q.append(nx)

ans = []
for i in range(N):
    if dist[i] % 3 == 1:
        ans.append(len(G[i]))

ans.sort()
print(*ans)

青色diff以上は後日挑戦