abc147_e Balanced Path

原因

bitsetがこんなに速いとは知らなかった

問題

https://atcoder.jp/contests/abc147/tasks/abc147_e

$H \times W (\le 80 \times 80)$ のマス目に $T_{ij} = \rm{abs} (A_{ij} - B_{ij}) \in [0,80]$ が書かれている。

$\left(1,1\right)$ から $\left(H,W\right)$ までマス目の下か右に移動する。このとき適当な移動経路上のマス目 $\left(i,j\right)$ について、$+ T_{ij}$ または $- T_{ij}$ の和を適切に取り、和の絶対値(:= 偏り)を可能な限り小さくする。考えられうる 偏り の最小値を求めよ。

解法

dp[i][j][k]をマス $\left(i,j\right)$ において偏りが $k$ になりうる、という真偽値で定義されるDPを考える。

この更新はbitsetを使うと非常に高速に実現でき、dp[i-1][j]とdp[i][j-1]をそれぞれ左右に$T_{ij}$だけシフトした値、合わせて4つ全ての $\rm{OR}$ をとれば求められる。初期値としてはdp[0][-1]において、偏りが0に相当する値のビットを立てておけばよい。

いま考えられうる偏りの最大値は $\max (H+W) \times T_{ij} = 12800$ だから、bitsetの幅として26000くらいを取っておけば十分。

事故

bitsetを使い慣れていなかったためmapで行けるでしょ、と考えて 1TLE。TLEの解消を小手先でやろうとして失敗、更に 2WA。

bitsetになってからもシフト幅が正じゃないとバグることを知らず1WA。ついでに無駄にDP領域をケチったため1WA。

計5ペナ。本番じゃなくて本当に良かった

対策： bitsetを細かいミスなくちゃんと使えるようになる。

bitsetでいけるって知ってたら瞬殺だったはずでは

提出コード

初AC: https://atcoder.jp/contests/abc147/submissions/9885352

リファイン版: https://atcoder.jp/contests/abc147/submissions/9887569

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (int i=0;i<(int)(n);i++)


int h,w;
int table[81][81], t; // 0-indexed

bitset<26000> dp[81][81]; // 1-indexed

signed main(){
    cin >> h >> w;
    REP(i,h) REP(j,w) cin >> table[i][j];
    REP(i,h) REP(j,w){
        cin >> t;
        table[i][j] = abs(table[i][j] - t);
    }
    dp[0][1][13000] = 1;
    REP(i,h) REP(j,w){
        dp[i+1][j+1] |= (dp[i+1][j] << table[i][j]);
        dp[i+1][j+1] |= (dp[i+1][j] >> table[i][j]);
        dp[i+1][j+1] |= (dp[i][j+1] >> table[i][j]);
        dp[i+1][j+1] |= (dp[i][j+1] << table[i][j]);
    }
    int ret = 20000;
    REP(ind,26000) if(dp[h][w][ind]) ret = min(ret, abs(13000-ind));
    cout << ret << endl;
}

感想

こういうときの F に限って考察が詰まらずにサクサク解けたので、本番だったらとても辛かったと思う