問題
二人のプレイヤーがいて、サイズN()の数列が与えられる。交互に配列に対して操作を行い、操作ができなくなったプレイヤーが負けとなる。操作は以下となる。
- 2以上の値を持つ要素を選ぶ
- この要素を空ではない2つの要素に分割
- 最初に選んだ要素を含まない2つの要素を選び、分割した要素の値を足す
最初のプレイヤーが勝つか負けるかを求めよ。
解法
全ての要素が2以上だと仮定すると、偶数の場合は最初のプレイヤーが負けてしまう。
値が1の要素が加わったとしても、最初に要素を選ぶことができたなら同様の結果となる。
計算量