自分用メモ

プログラミングとかのメモを書きたいです

競プロ典型 90 問:079 - Two by Two(★3)

問題

atcoder.jp

挑戦結果

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

考えたこと

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

公式解説

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')