AtCoder の問題を解くために必要な実力を付けるために作られた「典型問題」を解いていく企画として、「典型90」があります。
今回は、その内、の79問目である「079 – Two by Two（★3）」を解説していきたいと思います。
なにか、間違っているところなどありましたら、@EitaSugiまで、ご指導ご鞭撻の程、よろしくお願い致します！
問題名 【079 – Two by Two（★3）】
問題概要
H×W の2次元配列 A が与えられます。2種類の操作を行い、配列 A を配列 B に一致させることが目的です。操作は以下の通りです：
- 整数 x,y(1≤x<H,1≤y<W) を選び、Ax,y,Ax+1,y,Ax,y+1,Ax+1,y+1 の値をそれぞれ1ずつ増やす。
- 整数 x,y(1≤x<H,1≤y<W) を選び、Ax,y,Ax+1,y,Ax,y+1,Ax+1,y+1 の値をそれぞれ1ずつ減らす。
考察
影響範囲の理解
一つのセルを更新すると、そのセルを左上としたときの右上、左下、右下の3つのセルにも影響が出ます。この性質を利用して、左上から順に更新をかけることを考えます。
なぜなら、右から更新しても、左を更新する際に、また値の更新がされるためです。
しかし、左から更新すれば、左上の値は、それ以降更新されることがないです。
更新の方針
右や下から編集しても、左のセルを変更する際に影響が出てしまうため、左上から順に更新をかけることが有効です。一度操作したセルは、以降、値の変更は行われないため、効率的に操作を行うことができます。
コード
H,W = map(int, input().split())
A = []
B = []
for i in range(H):
w = list(map(int, input().split()))
A.append(w)
for i in range(H):
w = list(map(int, input().split()))
B.append(w)
cnt = 0
for i in range(H-1):
for j in range(W-1):
if A[i][j] == B[i][j]:
continue
elif A[i][j] > B[i][j]:
diff = A[i][j] - B[i][j]
for k in range(2):
for l in range(2):
A[i+k][j+l] -= diff
cnt += abs(diff)
elif A[i][j] < B[i][j]:
diff = A[i][j] - B[i][j]
for k in range(2):
for l in range(2):
A[i+k][j+l] -= diff
cnt += abs(diff)
if A == B:
print("Yes")
print(cnt)
else:
print("No")まとめ
前の問題【076 – Cake Cut（★3）】
次の問題【】
コメント