Problem p02839 (python)

Fixed submission:
# https://atcoder.jp/contests/abc147/submissions/8871745
# 写経
# bitset 高速化

def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1 << UPPER_BOUND_TOTAL_BIAS
    # dp[r][c]:(r,c)で値の加減を行った後、
    # 達成可能なbiasに該当するbitを立てたbit表現
    # 2**UPPER_BOUND_TOTAL_BIASの位をbias=0とみなす

    # -UPPER_BOUND_TOTAL_BIAS, ..., 0, ...UPPER_BOUND_TOTAL_BIAS [意味するbias]
    # 0, ..., UPPER_BOUND_TOTAL_BIAS, ..., UPPER_BOUND_TOTAL_BIAS*2 [dpに代入されるbit表現の桁]

    # numpyのndarrayを使用しなかった理由
    # dtypeでuint64を採用しても、
    # 2**(UPPER_BOUND_TOTAL_BIAS*2)は収まらない
    # pythonのintなら収まる

    for r in range(H):
        for c in range(W):
            x = dp[r][c]
            if r > 0:
                x |= dp[r - 1][c]
            if c > 0:
                x |= dp[r][c - 1]
            # x:(r,c)到達可能なbiasのbit表現

            d = D[r][c]
            dp[r][c] = (x << d) | (x >> d)
            # (r,c)マスでのbias変化を加味したbit表現

    ret = min(
        abs(UPPER_BOUND_TOTAL_BIAS - shift)
        for shift in range(UPPER_BOUND_TOTAL_BIAS * 2)
        if (dp[H - 1][W - 1] & (1 << shift)) > 0)

    print(ret)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = np.zeros(shape=(H, W, UPPER_BOUND_TOTAL_BIAS * 2 + 1), dtype=np.bool_)
    d = D[0][0]
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS - d] = 1
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS + d] = 1

    for r in range(H):
        for c in range(W):
            d = D[r][c]
            if r > 0:
                dp[r, c, d:] |= dp[r - 1, c, :-d]
                dp[r, c, :-d] |= dp[r - 1, c, d:]
            if c > 0:
                dp[r, c, d:] |= dp[r, c - 1, :-d]
                dp[r, c, :-d] |= dp[r, c - 1, d:]

    t = dp[H - 1, W - 1, :]
    indices = np.where(t == 1)[0]  # 一次元
    ret = np.abs(indices - UPPER_BOUND_TOTAL_BIAS)
    print(np.min(ret))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = np.zeros(shape=(H, W, UPPER_BOUND_TOTAL_BIAS * 2 + 1), dtype=np.uint8)
    d = D[0][0]
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS - d] = 1
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS + d] = 1

    for r in range(H):
        for c in range(W):
            d = D[r][c]
            if r > 0:
                dp[r, c, d:] |= dp[r - 1, c, :-d]
                dp[r, c, :-d] |= dp[r - 1, c, d:]
            if c > 0:
                dp[r, c, d:] |= dp[r, c - 1, :-d]
                dp[r, c, :-d] |= dp[r, c - 1, d:]

    indices = np.where(dp[H - 1, W - 1, :] == 1)
    t = tuple(abs(idx - UPPER_BOUND_TOTAL_BIAS) for idx in indices)
    print(np.min(t))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = np.zeros(shape=(H, W, UPPER_BOUND_TOTAL_BIAS * 2 + 1), dtype=np.bool_)
    d = D[0][0]
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS - d] = 1
    dp[0, 0, UPPER_BOUND_TOTAL_BIAS + d] = 1

    for r in range(H):
        for c in range(W):
            d = D[r][c]
            if r > 0:
                dp[r, c, d:] |= dp[r - 1, c, :-d]
                dp[r, c, :-d] |= dp[r - 1, c, d:]
            if c > 0:
                dp[r, c, d:] |= dp[r, c - 1, :-d]
                dp[r, c, :-d] |= dp[r, c - 1, d:]

    indices = np.where(dp[H - 1, W - 1, :] == 1)
    t = tuple(abs(idx - UPPER_BOUND_TOTAL_BIAS) for idx in indices)
    print(np.min(t))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def solve():
    import numpy as np
    import sys

    input = sys.stdin.readline

    h, w = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(h * 2)]
    for r in range(h):
        for c in range(w):
            d[r][c] = abs(d[r][c] - d[r + h][c])

    MaxBias = 80 * (h + w)

    dp = np.zeros(shape=(h, w, MaxBias + 1))
    dp[0, 0, d[0][0]] = 1

    for r in range(1, h):
        for bias in range(MaxBias + 1):
            if dp[r - 1, 0, bias]:
                for new_bias in abs(bias + d[r][0]), abs(bias - d[r][0]):
                    if 0 <= new_bias <= MaxBias:
                        dp[r, 0, new_bias] = 1

    for c in range(1, w):
        for bias in range(MaxBias + 1):
            if dp[0, c - 1, bias]:
                for new_bias in abs(bias + d[0][c]), abs(bias - d[0][c]):
                    if 0 <= new_bias <= MaxBias:
                        dp[0, c, new_bias] = 1

    for r in range(1, h):
        for c in range(1, w):
            for bias in range(MaxBias + 1):
                if dp[r - 1, c, bias] or dp[r, c - 1, bias]:
                    for new_bias in abs(bias + d[r][c]), abs(bias - d[r][c]):
                        if 0 <= new_bias <= MaxBias:
                            dp[r, c, new_bias] = 1

    for bias in range(MaxBias + 1):
        if dp[h - 1, w - 1, bias]:
            print(bias)
            return


if __name__ == '__main__':
    solve()