abc 147 E - Balanced Path (python)

解法１
dp[ i ][ j ][ k ] : i 行 j 列まで見たときに差が k になれるかどうか、なれるなら１、なれないのなら０を記録する。遷移は c = abs(a[ i ][ j ] - b[ i ][ j ]) として
(dp[i+1][ j ][k+c] = 1, dp[i+1][ j ][abs(k-c)] = 1 if dp[ i ][ j ][ k ] == 1) となる。
計算量は h*w*max(k) = 80**4 となる。pypy で def main(): つけたら通った。
解法２
dp[ i ][ j ] : i 行 j 列で実現可能な差を０と１との数列で保存する。
（例えば、dp[ i ][ j ] = 0010110 なら差を 1,2,4, にすることができるということ。）
遷移は dp[i][j] |= (dp[i][j-1]＜＜c | dp[i][j-1]＞＞c),
dp[i][j] |= (dp[i-1][j]＜＜c | dp[i-1][j]＞＞c)となる。
dp の初期値や求める答えに注意。計算量は h*w 余裕で通る。

#147-E -1
def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()

#147-E -2
import sys
input = sys.stdin.readline
h,w = map(int,input().split())
a = []
for i in range(h):
  s = list(map(int,input().split()))
  a.append(s)
  
b = []
for i in range(h):
  s = list(map(int,input().split()))
  b.append(s)
  
dp = [[0]*w for i in range(h)]
t = 80*(h+w)
dp[0][0] = 2**(t+abs(a[0][0]-b[0][0]))

for i in range(h):
  for j in range(w):
    r = abs(a[i][j]-b[i][j])
    if j > 0:
      dp[i][j] |= (dp[i][j-1]<<r | dp[i][j-1]>>r)
    if i > 0:
      dp[i][j] |= (dp[i-1][j]<<r | dp[i-1][j]>>r)
      
a = dp[h-1][w-1]>>t
m = a&(-a)
print(m.bit_length()-1)