ABC-147 E

解説通りのO(HW(H + W)M) をRubyで書くとTLEした(コンテストは不参加)のでbetrue12さんのを参考に読み解いてみたら、震えた。

atcoder.jp

取りうる差分をビットで表して、右ビットシフト、左ビットシフトで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 }