競プロ典型 90 問：079 - Two by Two（★3）

問題

atcoder.jp

挑戦結果

• 挑戦日：2021/11/01
• 結果：解けた
• 時間：10分

考えたこと

• 一番右下1箇所だけ更新してよいのか？を迷った。
  • そうだとすると、どんな場合もBに一致できそうだし、例とその答えとも一致しなくなるので、あくまで4箇所更新が必須という前提かと思った。
• Aの左上から順番、Bに寄せていく作業をやってみて、その回数をカウントすれば良さそう
• 最後までやってみて、Bに一致すればその回数が最短手数になるし、Bに一致しなければ不可能パターン(その場合は右下がずれる)。
• 例えば下記のようなことを繰り返す感じ。
  • をに寄せる。(その際、 も更新)
  • をに寄せる。(その際、 も更新)
  • ・・・

公式解説

https://twitter.com/e869120/status/1410007233262276612/photo/1

解説を読んだふりかえり

• キーワード：操作順序によらない

ソース

H,W= [int(x) for x in input().split()]
A,B = [],[]

for _ in range(H):
    a = [int(x) for x in input().split()]
    A.append(a)

for _ in range(H):
    b = [int(x) for x in input().split()]
    B.append(b)


cnt = 0
# 左上から合わせていく。一致できない場合は右下が一致しない。
for w in range(W-1):
    for h in range(H-1):
        diff = B[h][w] - A[h][w]
        A[h][w] += diff
        A[h+1][w] += diff
        A[h][w+1] += diff
        A[h+1][w+1] += diff
        cnt += abs(diff)

if A==B:
    print('Yes')
    print(cnt)
else:
    print('No')