🐶
ABC232解説：本番でACできた問題＋2問（Python）
A - QQ solver
最初と最後の文字をスライドで求め、整数型にして掛け算を行います。
a.py
S = input()
print(int(S[0]) * int(S[-1]))
evalを用いて文字列のまま処理することもできます。
a-eval.py
print(eval(input().replace("x", "*")))
B - Caesar Cipher
文字コードを考える方針が公式解説ですが、問題文に従って実直に解くこともできました。
まずアルファベットを保存する変数lettersを定義します。
ここでz->aの折返しもあるため、abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzと2回繰り返すことが肝となります。
次にKを求めます。
Sの頭文字sがlettersのどこに現れるのかを求め、そこからTの頭文字tは何番目に現れるのかを求めます。
あとは頭文字以外の数に対してはSをK移動させた値がTになるかを判定すればOKです。
b.py
S = input()
T = input()
letters = "abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"
s = S[0]
t = T[0]
k = 0
for i, l in enumerate(letters[letters.index(s) :]):
if l == t:
k = i
break
ans = "Yes"
for s, t in zip(S[1:], T[1:]):
if t != letters[letters.index(s) + k]:
ans = "No"
break
print(ans)
C - Graph Isomorphism
隣接行列と順列を使うことがポイントです。
隣接行列を用いることでグラフ間の(i,j)の結合のありなしを
なお、隣接リストを用いると非常に難しくなります。私の力量では解くことができませんでした。
順列はPythonではitertools.permutationsを用いると一行で書くことができます。
また、真偽値を保持する変数flagを用意し、for文を抜けた先でflagを評価するという書き方は競プロ典型です。
c.py
from itertools import permutations
N, M = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(M)]
CD = [tuple(map(int, input().split())) for _ in range(M)]
# 隣接行列 (頂点N、辺M)
GAB = [[False] * N for _ in range(N)]
for i in range(M):
a, b = AB[i]
GAB[a - 1][b - 1] = True
GAB[b - 1][a - 1] = True
GCD = [[False] * N for _ in range(N)]
for i in range(M):
a, b = CD[i]
GCD[a - 1][b - 1] = True
GCD[b - 1][a - 1] = True
for per in permutations(range(N)):
flag = True
for i in range(N):
for j in range(N):
if GAB[per[i]][per[j]] != GCD[i][j]:
flag = False
break
if flag:
print("Yes")
exit()
print("No")
D - Weak Takahashi
いわゆる配るDPで解きました。
DPテーブルに余裕をもたせることで配列外参照を気にする必要がないため、個人的には貰うDPよりも書きやすく感じます。
しかし、余裕をもたせた箇所は考慮しない点に注意が必要です。
以下は入力例1に対して配るDPを行ったあとのDPテーブルですが、灰色の箇所は除く必要があります。
実は本問では除かなくともACできますが、考慮したほうが無難だと思います。
d.py
H, W = list(map(int, input().split()))
C = [tuple(input().rstrip()) for _ in range(H)]
# 1行の余裕をもたせたDPテーブルを作ります。
dp = [[-1] * (W + 1) for _ in range(H + 1)]
dp[0][0] = 0
for i in range(H):
for j in range(W):
if C[i][j] == "#":
continue
if dp[i][j] == -1:
continue
dp[i][j + 1] = dp[i][j] + 1
dp[i + 1][j] = dp[i][j] + 1
ans = 0
# DPテーブルで余裕をもたせた箇所は除きます
for x in dp[:-1]:
ans = max(ans, *x[1:])
print(ans)
Discussion