https://atcoder.jp/contests/abc147/submissions/12449956
- 数値の範囲が
程度で小さいときはビットで表現する定石がある
- データ範囲をビットで表現すると 数値の加減算=ビットシフト で処理できる
各マス赤か青か2択あるので素直に実装するとの組み合わせになってしまう。右と下しか遷移がないことから動的計画法で処理することを考えてみる。各マス青と赤の２値あるが、絶対値で表現すると各マス１値に考え直すことができる。制約から意外と偏りのデータ範囲が[-25600, 25600]で狭く、ビットで表現する工夫をする。
dp配列の型をbitset<25600 * 2 + 1>とする。dp[y][x] := マス[y][x]における偏りbit組み合わせ と定義すると、加減算を以下のようにビットシフトで処理することができる。
dp[y][x] |= (dp[y - 1][x] << grid[y][x]);
dp[y][x] |= (dp[y - 1][x] >> grid[y][x]);
たいていのマスは2つの遷移元があるため１のビットは増加していくことが多い。最終的に１になってるビットのうち、真ん中（＝ゼロ）に最も近い値が答えになる。
なお、実装が多少増えるが、bitsetでなくbool型で実装することも出来る。
