後手必勝の必要十分条件は、\(1\) が連続する極大区間の長さが全て \(2\) である(もしくは全ての要素が \(0\) である)ことです。

実際、以下のことを用いて数学的帰納法で示すことができます。

• \(1\) が連続する極大区間の長さが全て \(2\) であるとき :
  • どのように操作をしても、いずれかの区間の長さが \(2\) でない状態になります。
• \(1\) が連続する極大区間の長さが \(2\) でないものがあるとき :
  • 極大区間の長さが \(1\) のものについては \(0\) にして消すことができます。
  • 極大区間の長さが \(3\) 以上のものについては、うまく選ぶことで複数の長さ \(2\) の区間に分けることができます。
    長さ \(4\) の例 : \((1,1,1,1) \rightarrow (0,1,1,0)\)
    長さ \(5\) の例 : \((1,1,1,1,1) \rightarrow (1,1,0,1,1)\)
  • 上記のような極大区間が複数ある場合でも、それぞれ独立に同時に操作を行えるため、極大区間の長さが全て \(2\) である(もしくは全ての要素が \(0\) である)状態にする操作が存在します。

どちらが勝つかどうかの判定は \(O(N)\) で行うことができます。