AtCoder Beginner Contest 147E問題

\(\def \set #1#2{\{ #1 \ \vert \ #2 \}}\)

ABC147E

解法

absでなく差で考える． 基本は部分和と同じ様に解ける． つまり，

\(dp_{i,j} := \) マス\(\ (i,j)\ \) にいるときの 偏り全体

とする．

実装

集合でなく bitset を使うと高速化出来る．

使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"

int main() {

  ll h,w; cin >> h >> w;

  vvll a(h, vll(w));

  cinvv(a);

  rep(i,h) rep(j,w){

    ll x; cin >> x;

    ll* p = &(a[i][j]);

    *p = abs(*p - x);

  }

  const ll shift = 160*80 + 5;  // shift

  const ll c = 2*shift + 5;

  using B = bitset<c>;

 

  vector<vector<B>> dp(h+1, vector<B>(w+1));

  { // AC

    dp[0][0].set(shift, 1);

    rep(x,h) rep(y,w){

      ll d = a[x][y];

      B now = dp[x][y];

      dp[x+1][y] |= (now << d);

      dp[x+1][y] |= (now >> d);

      dp[x][y+1] |= (now << d);

      dp[x][y+1] |= (now >> d);

    }

    dp[h][w] |= dp[h-1][w];

    dp[h][w] |= dp[h][w-1];

  }

 

  ll ans = shift;

  rep(d, shift){ // 答えを全探索

    if(dp[h][w][shift+d]) chmin(ans, d);

    if(dp[h][w][shift-d]) chmin(ans, d);

  }

  cout << ans << endl;

 

  return 0;

}