ABC147 E - Balanced Path

問題原文

atcoder.jp

問題要旨

縦 、横 マスのグリッドが与えられる。各マスには二つの数字、 と、 が設定されている。
一番左上のマスから、「右に移動」「下に移動」を繰り返して、一番右下のマスを目指す。
あるマスを通った時、そこに書かれている数字の１つを赤色、１つを青色で塗る。
最適に経路と塗り分け方を選んだ時の、「赤く塗られた数の総和 と 青く塗られた数の総和、の差の絶対値の最小値」はいくつになるか？

• 
• 

解法

「赤く塗られた数の総和 と 青く塗られた数の総和、の差の絶対値」だと長いしつかいにくいので、を以後 偏りとする。
:= 上から 、左から マスに移動した時点で、偏りを にできるか？

を考えます。 遷移は、 各マスの２数の差の絶対値を として計算しておけば、
=

• 
• 
• 
• 

にように計算できる。 式はなんか難しそうだけど、要するに「１つ上 or １つ左のマスから、今みている偏りを良い感じにすることで、偏り を達成できるか？」ということですね。

実装

考えうる偏りの範囲を雑に考えると、 80（縦最大） × 80（横最大） × 80（各マスの最大の偏り）× 160（最大何回移動する必要があるか）≒ 8000万 ぐらいになって、Pythonだとまぁ間に合わない。。。（C++とかならこのまま殴れると思う）

そこで dpテーブルの定義を変えて、
:= 上から 、左から マスに移動した時点で 実現可能な偏りの集合 とする。
すると、前半のほとんど実現不可能な部分からの遷移を考える必要がなくなる。
また遷移は、
- , の全要素について、 を加算したもの and 減算して絶対値をとったもの

とすればいい。
PyPy2 + 地道な高速化を積んで、1603msでした。
ほんとは numpyを使うべきなんだけどね。。。

def main():
    import sys

    H, W = map(int, sys.stdin.readline().split())
    A = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    B = [list(map(int, sys.stdin.readline().split())) for i in range(H)]
    X = [[0] * W for i in range(H)]
    for h in range(H):
        for w in range(W):
            X[h][w] = abs(A[h][w] - B[h][w])

    dp = [[set() for j in range(W)] for i in range(H)]
    dp[0][0].add(X[0][0])
    dp[0][0].add(-X[0][0])

    for h in range(H):
        for w in range(W):
            if h == 0 and w == 0:
                continue
            x = X[h][w]
            s = set()

            if h > 0:
                for d in dp[h - 1][w]:
                    s.add(d + x)
                    s.add(abs(d - x))

            if w > 0:
                for d in dp[h][w - 1]:
                    s.add(d + x)
                    s.add(abs(d - x))

            dp[h][w] = s

    ans = min([abs(s) for s in dp[H - 1][W - 1]])
    print(ans)


if __name__ == '__main__':
    main()

感想

考察というよりは、実装が大変な問題でした。。。いい勉強になりました 。
dpテーブルを辞書: setで持つよりも、 dp[i][j] = set の形で持つ方が早いのは知見でしたね。