7K4B blog

猫でも分かる何か

ABC147 E - Balanced Path

f:id:tkr987:20200602142925p:plain

https://atcoder.jp/contests/abc147/submissions/12449956

  • 数値の範囲が -2 \times 10^4, 2 \times 10^4程度で小さいときはビットで表現する定石がある
  • データ範囲をビットで表現すると 数値の加減算=ビットシフト で処理できる

f:id:tkr987:20200602145730p:plain

各マス赤か青か2択あるので素直に実装すると 2^{6400}の組み合わせになってしまう。右と下しか遷移がないことから動的計画法で処理することを考えてみる。各マス青と赤の2値あるが、絶対値で表現すると各マス1値に考え直すことができる。制約から意外と偏りのデータ範囲が[-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つの遷移元があるため1のビットは増加していくことが多い。最終的に1になってるビットのうち、真ん中(=ゼロ)に最も近い値が答えになる。

 

なお、実装が多少増えるが、bitsetでなくbool型で実装することも出来る。

https://atcoder.jp/contests/abc147/submissions/13933546