Pythonで競プロに挑む日誌 vol.20 ~小分けにして考える~

現在の目標

• 2018年内に茶色になる←イマココ
• ABC の A, B 問題を全部解く
• 2018年度内に緑色を取得する
• 水色になったら, APG4b で C++ にも手を出す

今日のおはなし

結論

ややこしそうな問題は, やりたいことを小分けにして一個ずつ処理しよう.

解いた問題

B - Template Matching

頭がこんがらがっていた解答

WA.py

 coding: utf-8
N, M = map(int, input().split())
A = "".join([input() for _ in range(N)])
B = "".join([input() for _ in range(M)])
 
ans = "No"
w = ""
for i in range(0, len(A), N):
    for j in range(N-M):
        w += A[i+j:i+j+M]
        if w == B:
            ans = "Yes"
            break
print(ans)

テンプレ B と同じサイズの窓 W を定義して, その窓で画像 A を順にくりぬいて, そのくりぬき部分が B と合致していたら Yes とするつもりでした.
for ループの条件とか, 窓の切り抜き方を並行して考えてるうちに, 頭がこんがらがってしまいました.

やることを分割

「正方形の窓を移動させて判定する」というアプローチは良かったのですが, 実現するまでの道筋がよくなかった模様. 先人のコードを拝見して,

• 「正方形窓で画像 A の一部を切り取り, テンプレ B と比較する機能」

と,

• 「窓を移動させるための制約条件 (for ループの条件)」

を分けて考えるのがよさそうに思いました.

AC.py

# coding: utf-8
def match(ofs_x, ofs_y, li_A, li_B):
    for a, b in zip(li_A[ofs_y:], li_B):
        if a[ofs_x:ofs_x + M] != b:
            return False
    return True
 
N, M = map(int, input().split())
li_A = [input() for _ in range(N)]
li_B = [input() for _ in range(M)]
 
for y in range(N-M+1):
    for x in range(N-M+1):
        if match(x, y, li_A, li_B):
            print("Yes")
            exit()
print("No")

ほぼコピペになってしまいましたが, 「窓を移動させる機能」を先に用意することで, あとは窓がどれだけ移動するか考えればよいことになります。今回の場合は, 横(x 方向), 縦(y 方向) ともに N-M+1 まで変化するので, それを for ループの条件にしてあげればよいですね.

むすび

めんどくさそうなことでも, 小分けにしていけばいつかは解ける.