ABC232
$ S[0\rbrack \times S[-1\rbrack
文字列で受けて先頭と末尾を取り出し、int()に入れて計算。 $ 0,\dots,25の数列に変換して、$ T[0\rbrack-S[0\rbrackで$ Kを計算。あとは実際に操作を行ってみて、$ S==TならYes。
code: b.py
def str_to_int(s):
return ord(s) - ord("a")
S = list(map(str_to_int, input()))
T = list(map(str_to_int, input()))
for i in range(len(S)):
print("Yes" if S==T else "No")
グラフが同型がどうか判定せよ。という問題。
『グラフ 同型判定』で調べてもとくに（競プロ文脈で）良いアルゴリズムが見当たらないこと、$ Nの制約が非常に小さいことから、ありえる頂点の順番を全探索して判定問題にする。
高橋君は右か下にしか行けないので、単純なDPで計算できる。
$ DP[i\rbrack[j\rbrack \coloneqqマス$ (i,j)までに訪れることのできるマスの数の最大値。
$ DP[i\rbrack[j\rbrack = max(DP[i-1\rbrack[j\rbrack, DP[i\rbrack[j-1\rbrack)+1
ただし、壁のマスは計算しない、値が0であるようなマスからは遷移しない。
愚直実験コードを書いて様子を眺めてみる。すると、状態の数は4通りしかないことに気がつく。
4つの状態とはすなわち、$ x_1,y_1と
①行も列も一致しているマス$ (x_1, y_1)
②行のみ一致しているマス$ (x_1, Y)
③列のみ一致しているマス$ (X, y_1)
④行も列も一致していないマス$ (X, Y)
あとはそれぞれがそれぞれにどのように遷移するかを追っていくと、答え。
$ DP[k\rbrack[i\rbrack[j\rbrack \coloneqq$ k回目の移動時点で$ (x_1, y_1)と行が一致$ i(bool)しているか、列が一致$ j(bool)しているマスへの移動のしかたの通り数。
計算量は$ O(K)