ABC-147 E
解説通りのO(HW(H + W)M) をRubyで書くとTLEした(コンテストは不参加)のでbetrue12さんのを参考に読み解いてみたら、震えた。
取りうる差分をビットで表して、右ビットシフト、左ビットシフトでORを取るDPしてた。すげぇ。
下記は理解後、自分で書いてみたコード
H,W = gets.split.map(&:to_i) M = (H + W) * 80 A = H.times.map { gets.split.map(&:to_i) } B = H.times.map { gets.split.map(&:to_i) } dp = Array.new(H){ Array.new(W, 0)} dp[0][0] = 1 << M W.times do |x| H.times do |y| d = (A[y][x] - B[y][x]).abs dp[y][x] = (dp[y][x] << d | dp[y][x] >> d) if x == 0 && y == 0 dp[y][x] |= (dp[y][x - 1] << d | dp[y][x - 1] >> d) if x > 0 dp[y][x] |= (dp[y - 1][x] << d | dp[y - 1][x] >> d) if y > 0 end end G = dp[H - 1][W - 1] puts M.times.find{|i| G[M - i] > 0 || G[M + i] > 0 }