AtCoder Beginner Contest 147：E - Balanced Path

問題
解法
解答

問題

https://atcoder.jp/contests/abc147/tasks/abc147_e

解法

dp(i, j, k) := マス (0, 0) からマス (i, j) までのパスで「偏り」が（以上でも以下でもなく）k となるかどうか

という DP を考えると，遷移は (0, 0, |A[0][0] - B[0][0]|) から始めて，

dp(i + 1, j, m1) = true

dp(i + 1, j, m2) = true

dp(i, j + 1, m1) = true

dp(i, j + 1, m2) = true

（ただし，m1 = |k - d|, m2 = k + d）

となる．m1, m2 は「偏り」が小さくなるか大きくなるかの 2 通りを試すことを意味している．答えは dp(H - 1, W - 1, k) が true であるような最小の k になる．「偏り」の最大が 80 * (H + W - 1) となるから，計算量は O(HW * 80(H + W - 1))．