ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder Grand Contest 048 D - Pocky Game

D - Pocky Game

解法

各山の石の個数について、その初期値を  A_{i} と表し、ゲームの途中経過における値を  a_{i} と表すことにします。

まずは全ての状態を網羅するDPを

もし石の総数が十分少なければ、以下のDPで全ての局面の勝敗状態を求めることができます。

  •  dp_{1}\lbrack l\rbrack\lbrack r\rbrack\lbrack a_{l}\rbrack\lbrack a_{r}\rbrack:「先手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  l の石の個数が  a_{l}、山  r の石の個数が  a_{r} である」という状態が先手勝ちであればtrue、後手勝ちであればfalse。
  •  dp_{2}\lbrack l\rbrack\lbrack r\rbrack\lbrack a_{l}\rbrack\lbrack a_{r}\rbrack:「後手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  l の石の個数が  a_{l}、山  r の石の個数が  a_{r} である」という状態が後手勝ちであればtrue、先手勝ちであればfalse。

当然ながらこれでは状態数が多すぎるので減らす方法を考えます。

単調性に気付く

1個以上の石が残っている山の番号が  l から  r までである状態をまとめて考えます。このとき、先手は自分が操作する山  l に残っている石  a_{l} が多いほど有利です(それ以外の状況が全く同じである場合)。同様に後手は山  r に残っている石  a_{r} が多いほど有利です。石が多い状態からは、余分に石を取ることで石が少ない状態と同じ遷移ができるからです。

この性質を利用すると、自分側の石の個数をキーではなく値の方に持つ、以下のようなDPの状態を考えることができます。

  •  dp_{1}\lbrack l\rbrack\lbrack r\rbrack\lbrack a_{r}\rbrack:先手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  r の石の個数が  a_{r} であるとき、山  l の石の個数がこの値以上であれば先手勝ち、そうでなければ後手勝ちである。
  •  dp_{2}\lbrack l\rbrack\lbrack r\rbrack\lbrack a_{l}\rbrack:後手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  l の石の個数が  a_{l} であるとき、山  r の石の個数がこの値以上であれば後手勝ち、そうでなければ先手勝ちである。

これは「bool値を持つDPで、あるキーについて単調性がある場合、そのキーを値にすることで状態数を減らせる」という汎用性の高いテクニックです。ですがこれでもまだ間に合わないのでさらに状態を削ります。

「山の石を取り切った瞬間」だけを考える

1ターンずつ全ての状態を考えていると間に合わないので、ゲームにおいて区切りとなるような状態だけ考えて、それらの勝敗判定ができないか考えます。

ゲームの流れを大雑把に区切ると、「いずれかのプレイヤーが自分側の山の石を全て取り切る」というイベントが合計  N 回起こります。このように相手が山の石を全て取り切って自分にターンが回ってきた瞬間には、相手側の次の山には石が全て残っています(石が残っている山が1個以下になる場合を除く)。このような状態だけをピックアップします。

  •  dp_{1}\lbrack l\rbrack\lbrack r\rbrack:先手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  r の石の個数が初期値  A_{r} のままであるとき、山  l の石の個数がこの値以上であれば先手勝ち、そうでなければ後手勝ちである。
  •  dp_{2}\lbrack l\rbrack\lbrack r\rbrack:後手の手番で、1個以上の石が残っている山の番号が  l から  r までで、山  l の石の個数が初期値  A_{l} のままであるとき、山  r の石の個数がこの値以上であれば後手勝ち、そうでなければ先手勝ちである。

ただし石が残っている山が1個である場合は個数に関わらず石を全部取り切って勝てるので、全ての  i について  dp_{1}\lbrack i\rbrack\lbrack i\rbrack = dp_{2}\lbrack i\rbrack\lbrack i\rbrack = 1 とします。これがDPの初期状態です。

これでようやく状態数が  O(N^{2}) になります。ですが1手ずつの状態を考えていないので、遷移を求めるのに工夫が必要です。

遷移計算

 dp_{1}\lbrack l\rbrack\lbrack r\rbrack の求め方を考えます。もう片方も同様です。

まず、それぞれのプレイヤーが取る行動としては「1個だけ取る」「山の石を全部取る」の2通りだけ考えれば十分であることが分かります。他の条件が同じであれば自分側の山の石が多いほうが有利なので、取り切らないのに2個以上取るという行動は自分を不利にするだけだからです。

もしいきなり先手が全取りして勝ち状態に持っていける場合は、 dp_{1}\lbrack l\rbrack\lbrack r\rbrack = 1 です。こうなる条件は、全取りすることで後手に渡す状態が後手にとって負け状態であること。つまり  dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack \gt A_{r} であることです。

そうでない場合、先手が1個取り、後手が1個取り…という行動を繰り返してそれぞれの石が減っていき、「ここで全取りすれば勝ち」という状態に先になったほうが勝ちます。先手側の山  l にある石の個数を  x とすると、こうなるまでの行動回数は

  • 先手が全取りで勝てるようになるまでに必要な後手の行動回数: a_{r}=A_{r} から始まって  dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack \gt a_{r} を満たす状態まで減って欲しいので、 A_{r}-dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack+1 回必要。
  • 後手が全取りで勝てるようになるまでに必要な先手の行動回数: a_{l}=x から始まって  dp_{1}\lbrack l\rbrack\lbrack r-1\rbrack \gt a_{l} を満たす状態まで減って欲しいので、 x-dp_{1}\lbrack l\rbrack\lbrack r-1\rbrack+1 回必要。

と計算することができます。先手の手番であることを考慮すると、先手が勝てる条件は

 A_{r}-dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack+1 \lt x-dp_{1}\lbrack l\rbrack\lbrack r-1\rbrack+1

なので、 x が整数であることを考慮してこれを解くと

 x \ge dp_{1}\lbrack l\rbrack\lbrack r-1\rbrack + A_{r}-dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack+1

となります。

よって整理すると、 dp_{1}\lbrack l\rbrack\lbrack r\rbrack は以下のように求められます。

  •  dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack \gt A_{r} である場合、 1
  • そうでない場合、 dp_{1}\lbrack l\rbrack\lbrack r-1\rbrack + A_{r}-dp_{2}\lbrack l+1\rbrack\lbrack r\rbrack+1

これで遷移が計算できるので、区間が狭い方から順番に求めていきます。最終的に先手が勝つ条件は  A_{1} \ge dp_{1}\lbrack 1\rbrack\lbrack N\rbrack で判定することができます。

ACコード

Submission #17514189 - AtCoder Grand Contest 048