Atcoder ABC232 振り返り

　バーチャルで参加しました（196位）．Cに手こずりましたが，滅多に使わない隣接行列を使うと簡単だと気付いたらすぐに解けました．

A - QQ solver【AC】

　pythonは文字列と数字の変換が簡単で助かる．

s = input()
print(int(s[0])*int(s[2]))

B - Caesar Cipher【AC】

　文字とasciiコードの変換はord()関数を使う．aは97にzは122に変換される．zからaに写るような場合はaのasciiコードに26を足すことで適切に計算可能．

S = input()
T = input()
if ord(S[0]) > ord(T[0]):
    sa = ord(S[0]) - ord(T[0])
else:
    sa = ord(S[0])+26 - ord(T[0])

for i in range(1, len(S)):
    if ord(S[i]) > ord(T[i]):
        if sa != ord(S[i]) - ord(T[i]):
            print("No")
            break
    else:
        if sa != ord(S[i])+26 - ord(T[i]):
            print("No")
            break
else:
    print("Yes")

C - Graph Isomorphism【AC】

　頂点が8個しかないので隣接行列を使うのが楽．順列を使い対象の行と列をそれぞれ入れ替え，隣接行列が完全一致していれば同じグラフと言える．行の入れ替えはlis[i], lis[j] = lis[j], lis[i]とやればいいが，列の入れ替えはリストでやろうとすると簡単では無い．よってnumpyを使う．ndarrayなら[:, [3,2,1]]などとすれば，列を3,2,1に入れ替えたndarrayが出来る．ndarrayが完全一致しているか判定するにはnp.allcloseを使う．

import itertools
import numpy as np

N, M = map(int, input().split())
takahashi = [[0 for _ in range(N)] for _ in range(N)]
aoki = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    takahashi[a][b] = 1
    takahashi[b][a] = 1
for _ in range(M):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    aoki[a][b] = 1
    aoki[b][a] = 1

takahashi = np.array(takahashi)
aoki = np.array(aoki)

X = range(N)
for x in itertools.permutations(X, N):
    change_takahasi = takahashi[:, x]
    change_takahasi = change_takahasi[x, :]
    if np.allclose(aoki, change_takahasi):
        print("Yes")
        break
else:
    print("No")

D - Weak Takahashi【AC】

　幅優先探索で探索する．

from collections import deque
H, W = map(int, input().split())
tizu = []
masu_tizu = [[0 for _ in range(W)] for _ in range(H)]
for _ in range(H):
    tizu.append(list(input()))

que = deque([(0, 0)])
masu_tizu[0][0] = 1

while que:
    qx, qy = que.popleft()

    ok = False
    if qx + 1 < W:
        if masu_tizu[qy][qx+1] == 0 and tizu[qy][qx+1] == ".":
            ok = True
            masu_tizu[qy][qx+1] = masu_tizu[qy][qx] + 1
            que.append((qx+1, qy))
    if qy + 1 < H:
        if masu_tizu[qy+1][qx] == 0 and tizu[qy+1][qx] == ".":
            ok = True
            masu_tizu[qy+1][qx] = masu_tizu[qy][qx] + 1
            que.append((qx, qy+1))

print(max(sum(masu_tizu, [])))