ABC303-G Bags Game 解説

問題リンク

difficulty 高くない？（位置の影響かなあ）

解説

先手も後手も操作と最適化の内容が全く同じなので、適宜先手と後手を入れ替えて考えればよい。

• $dp[i][j] =$ 区間 $[i,j]$ から始め、互いが最適に行動したときの先手 - 後手の値

として区間 DP を考える。端しか取らない時の遷移は自明なので、まとめて $B$ 個か $D$ 個取る時の遷移が $o(N)$ になれば嬉しい。

DP 配列を幅ごとに分けて（直交座標にプロットしたら、斜めに切って）考えると、幅が一定の中で区間最小値を求めればいい。 実際は、これに対して、操作で取った分の値を足さなければならないが、先に $[i,j]$ 全体の総和を足して、区間最小を求める時に該当区間の総和を足した上で考えれば、全体として、再帰的に参照する小さな区間の外側の部分だけの総和が得られる。

セグ木で実装すれば $\mathrm{O}(N^2\log N)$ だが、スライド最小値を前計算しても解けるので、 $\mathrm{O}(N^2)$ まで落ちる。