Nim with Gold Coins

$A_1,A_2,...,A_N$ は降順にソートされているものとします。
最終的な金貨の所持数を最大化するには、自分の手番が回ってきたときに一番金貨の多い山の金貨を全て取れば良いです。
よって、$A_1+A_3\ldots > A_2+A_4+\ldots$ならば先手が勝ちます。
逆に、$A_1+A_3+... = A_2+A_4+...$ の場合は$A_1=A_2,A_3=A_4\ldots$ が成り立つので、後手が先手の真似、つまり先手の取った山と同じ枚数の金貨がある山から先手の取った枚数と同じ枚数だけ取ることを繰り返すことにより必ず先手と同じ枚数を入手した上で最後の金貨を取ることが出来るので、後手が勝ちます。
計算量はソートがボトルネックとなり $O(NlogN)$ です。