SRM384 Div2 1000

問題

AlanとBobが2つの山からスティックを交互に取り除くゲームをする．最初はAlanのターンから始まり，各プレイヤーは正確にn^2本のスティックを各山から取り除く．各山から取り除くスティックの本数は同じでなくてよい．(山1から1^2本，山2から3^2本などが可能)
最初にそのようなとり方ができなくなったプレイヤーの負けになる．

それぞれの山にあるスティックの本数がそれぞれsize0，size1で与えられる．
両者が最適にプレイした場合，最短で何ターンでどちらが勝つか．
(勝てる場合は早く勝とうとし，負ける場合は遅く負けようとする)

考え方

同時に取り除いていくが，山同士が独立しているので，山1と山2のターン数の少ないほうを求めればいいことがわかる．なので，山のsize本が最短で何ターンでどちらが勝つかをはんていすればよい．

i本のスティックがある状態で自分のターンになった場合，

• 「最後のスティックをとったら勝ち」＝「i=0なら負け」
• あるj本に対して，i-j*j本が負けならば，i本はその本数にすれば必ず勝てる
  • 一番ターン数の少なくなる本数を取り除く
• すべてのj本に対して，i-j*j本が勝ちならば，i本は勝つことができないので必ず負ける
  • 一番ターン数が多くなる本数を取り除く

というのをDPを使って計算すればよい．
この問題では，ターン数の偶奇によってどちらが勝つかがわかるので，DPはターン数を保持するようにすればよい．

反省

蟻本の上級編の「コインのゲーム1」とほぼ同じ感じ．dpが勝ち負けを保持するかターン数を保持するかの違い．

山が複数存在し，どの山かを選んでその山からだけ取り除く場合の勝敗判定はGrundy数を計算し，(Nimと見なすことができるので)そのXORが0かどうかをみればよい．