黒板に書かれている非負整数の多重集合を \(S=\lbrace s_1,s_2,\dots,s_k \rbrace\) で表します。

\(S\) が与えられたときの必勝プレイヤーは以下のように判定出来ます。

• 互いに操作を繰り返し行ったとき、先に以下の条件のいずれかを満たすターンに操作をするプレイヤーが必勝。
  • \(S = \lbrace 0 \rbrace\)
  • \(m \ge 2\)
  • \(S\) に \(0\) が \(2\) 個以上含まれる。

下の \(2\) 個の条件によって、条件をいずれも満たさない間は操作が一意であるため上記の必勝プレイヤーは一意に定まることに注意してください。

上記の事実を証明するには、上記のいずれかの条件を満たす \(S\) からゲームをするときに先手必勝であることを証明すれば十分です。

\(S = \lbrace 0 \rbrace\) であるときは自明です。

\(m \ge 2\) のときは、\(x = m\) を選んだときの盤面 \(S'=\lbrace s_1-m,s_2-m,\dots,s_k-m \rbrace\) からゲームを始めたときの必勝プレイヤーによって場合分けをします。

• $S'$ からゲームを始めたときに先手必勝の場合

先手は $x = m-1$ を選べばよいです。この操作によって、$m = 1$ となるため次のターンに後手が選べる操作は $x = 1$ を選ぶことのみです。その結果、先手に $S'$ が回ってくるため先手必勝です。

• $S'$ からゲームを始めたときに後手必勝の場合

先手は $x=m$ を選べばよいです。後手に $S'$ を回すことが出来るため、先手必勝です。

\(S\) に \(0\) が \(2\) 個以上含まれるときは、\(S\) に含まれる \(0\) の個数を \(c(\ge 2)\) と置き、\(0\) を \(c\) 個全て消したときの盤面 \(S'\) からゲームを始めたときの必勝プレイヤーによって場合分けをします。

• $S'$ からゲームを始めたときに先手必勝の場合

先手は $0$ を $c-1$ 個消せばよいです。この操作によって、$S$ は $0$ を $1$ 個のみ含む状態になるため次のターンに後手が選べる操作はその $0$ を消すことのみです。その結果、先手に $S'$ が回ってくるため先手必勝です。

• $S'$ からゲームを始めたときに後手必勝の場合

先手は $0$ を $c$ 個消せばよいです。後手に $S'$ を回すことが出来るため、先手必勝です。

よって、条件のいずれかを満たすときに先手必勝であることが証明出来ました。

与えられた \(A\) から必勝プレイヤーを判定するには、上記のいずれかの条件を満たす盤面になるまで操作をシミュレーションすればよいです。条件を満たしていない時に可能な操作は全体から \(1\) を引くことか、\(0\) を \(1\) 個のみ削除することなので \(A\) をソートしておき、今までに合計いくつを全体から引いたかを管理すればシミュレーション出来ます。

上記を実装することで計算量 \(\mathrm{O}(N \log N)\) でこの問題を解くことが出来ます。