E. Thanos Nim

Quiz

https://codeforces.com/contest/1162/problem/E

Submission

https://codeforces.com/contest/1162/submission/53797164

解法

  • まず、1つでも空にしてしまうと負けである
    • 次のターンに相手がN/2個を空にしてきて、自分はN/2個取れないので負ける
  • 1, 1, 1, 1などの明らかな負けを場合分けしていくと、ちゃんと考えるべきなのは
  • 11, 12, 13, 14 などである。この場合は
  • 11, 11, 11, 14 を押し付けることができる。相手は11の山から取ることを強制される
  • これを続けていくと相手は最初に山を1にしてしまう
  • 1を作ってしまった側は負けである
  • 例:1 5 5 5
  • 次のターンに1 1 1 5を押し付けられてしまい、山を空にすることを強制されてしまい、負ける
  • 配列の最小値のカウントで勝負が決まる
    • 例:11 12 13 14 ならカウントは1 => 11 11 11 14を押し付けることができるので勝ち
    • 例:13 13 20 30 ならカウントは2 => 13 13 13 13 を押し付けることができるので勝ち
    • 例:13 13 13 20 ならカウントは3 => 押し付けられている側なので負け

Nim

  • こういう石取りゲームは「Nim 競プロ」などで検索すると理論が出てくる
  • 今回の問題のタイトルにもNimと書かれている