きままにものづくり

日々の気付いたことなんかを書いてます。

SRM619Div1Easy

問題

二人のプレイヤーがいて、サイズN(N \leq 50)の数列が与えられる。交互に配列に対して操作を行い、操作ができなくなったプレイヤーが負けとなる。操作は以下となる。

  • 2以上の値を持つ要素を選ぶ
  • この要素を空ではない2つの要素に分割
  • 最初に選んだ要素を含まない2つの要素を選び、分割した要素の値を足す

最初のプレイヤーが勝つか負けるかを求めよ。

解法

全ての要素が2以上だと仮定すると、偶数の場合は最初のプレイヤーが負けてしまう。
値が1の要素が加わったとしても、最初に要素を選ぶことができたなら同様の結果となる。

計算量

O(N)

コード