ARC105 D - Let's Play Nim (600)
このNimは全ての皿のコインの枚数をXORした結果が0でなければ先手の勝利、0ならば後手の勝利
ある皿が全ての袋のコインの過半数の枚数になるとXORで0が作れなくなる
Nが偶数の場合、先手はある皿に残っている中で一番コインのある袋を追加すれば良い
同じ枚数入っている袋で全てがペアにならない限り、これによって過半数を作れるので先手の勝利
ペアなら先手が置いたのと対称になるように後手が同じ枚数を置くと、同数になってXORが0になり後手の勝利
Nが奇数の場合、先手がNimでは後手になるのでXORを0にしたい
後手は先手が最初に置いた皿に残っている中で一番コインのある袋を追加すれば必ず過半数を作れるので後手が必勝
最初に先手が置いた枚数の分をどうやっても覆すことができないため
全ての皿の枚数を見るだけなので$ O(N)