https://emtubasa.hateblo.jp/entry/2020/11/10/152101

解法

わかりやすい部分、つまり $N$ が小さい方から考えていきます。

$N = 1$ のとき

1回の操作で必ず1減少するので、明らかに、 $A_{1}$ の偶奇で答えが判定できます。
奇数であれば後手勝ち、偶数であれば先手勝ちです。

$N = 2$ のとき

$A_{i}$ のどちらかが1であった場合、先ほどと同様、もう片方の数字の偶奇で判定でき、奇数なら後手勝ち、偶数であれば先手勝ちです。
そうではない場合を考えます。順序は関係ないため、 $A_{1} \lt A_{2}$ であると仮定します。
$A_{1} = 2$ のとき、問題の条件より、 $A_{2}$ は3以上の奇数になります。
この時、 $A_{1}$ を先手が選ぶと、 $A_{1}$ が1になり、これ以降は $A_{2}$ を減らすことしか選べなくなります。ここで、 $A_{2}$ は開始時点で奇数であることが保証されていたため、結果としては必ず先手が勝つことになります。
$A_{1} = 3$ のときも見てみると、遷移先の勝敗を照らし合わせることで、
$(3,4),(3,8),(3,10)$ は先手勝ち、 $(3,5),(3,7)$ は後手勝ちであることがわかります。
この結果を踏まえると、どちらか片方が偶数であれば先手勝ち、奇数であれば後手勝ちであると予想が立てられます。
これが正しいことを証明していきます。
ゲームの最終状態は $(1,1)$ です。よって、両方奇数であれば負け、ということになります。
現在のゲームの状態に偶数が含まれている場合、その偶数を選んで1減らすことで、両方の数字が奇数になります(割り算で偶奇は変化しません)。
逆に、両方奇数である場合、どちらを選んでも、必ず偶数が残ってしまいます。
よって、偶数が含まれた状態でターンが回ってきた場合、相手に必ず両方の数字が奇数である状態を押し付けることができ、逆にそれがおしつけられた場合、相手には偶数が残った状態でターンを渡すことになります。
これにより、 $N=2$ のときは、偶数が含まれていれば先手勝ち、そうでなければ後手勝ちであることがわかりました。

$N \geq 3$ のとき

$A_{i}$ に1が含まれている際は、1ずつ減っていくだけなので、これは先ほどまでと同様に答えを求めることができるため省略します。
ここらから状態のパターンが多くなり複雑になっていくので、実験コードを書いて実験をしてみます。すると、 $N$ の偶奇でパターンがわかれていることがわかります。

$N$ が偶数のとき

$A_{i}$ に含まれる偶数の個数の偶奇で勝敗が決まっていることがわかります。
偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちです。
奇数個の状態で回ってきた人は、偶数を選び1減らすことで必ず相手に偶数個の状態でターンを回せます(選んだ偶数が必ず奇数になり、最大公約数が偶数になることはありません)。
逆に、偶数個の状態で回ってきた人は、偶数、奇数どちらを選んで1減らしても、偶数は奇数個になってしまいます。こちらのパターンも、 $N$ が偶数のため、奇数が必ず1つ含まれることになり、最大公約数が偶数になることはありません。
これにより、 $N$ が偶数のときには、 $A_{i}$ に含まれる偶数の個数が奇数であれば先手勝ち、偶数であれば後手勝ちであることがわかりました。

$N$ が奇数のとき

こちらも基本的には偶数パターンと同じ見た目をしています。
偶数の個数が $N-1$ でなければ、上記と同様の作戦をとることで勝敗が決まります。
しかし、偶数の個数が $N-1$ の場合、以下のような例が考えられます:

5
2 4 6 8 11

このようなパターンのとき、先手は11を選んで操作を行うと、

1 2 3 4 5

となります。これは、本来先手から始めた場合に後手が勝つパターンです。1回先手が操作をしているので、上記のケースは結局先手勝ち、ということになります。
つまり、 $N-1$ 個の偶数があった場合、1つだけある奇数を選んで操作することで、勝敗がひっくりかえることがあります。このパターンのみ、1つの奇数を選んで操作をする、ということをシミュレートし、勝敗がわかるまで繰り返せばよいです。
必ず偶数の最小公倍数になるため、一度の操作で全ての数字は半分以下になります。よって、操作は $O(\log A_{i})$ 回で収まり、十分間に合います。

これで勝敗の判定方法がわかったので、まとめます。

$N$ が1のとき
$A_{1}$ の偶奇で判定します。
上記以外で、 $A_{i} = 1$ となるような $i$ が存在
$\sum_{i} (A_{i} - 1)$ の偶奇で判定します。
上記以外で、 $N$ が偶数、もしくは $A_{i}$ の偶数の個数が $N-1$ でない
偶数の個数の偶奇で判定します。
上記以外( $N$ が奇数かつ、 $A_{i}$ の偶数の個数が $N-1$ 個
残った奇数を選び操作をするとしてシミュレートし、上記のパターンに帰着できるまで繰り返します。

という形です。

感想

苦手なゲーム問題で、実験コードを組みつつきちんと通せたので、良かったです。