東京工業大学プログラミングコンテスト2019：D - 素数取りゲーム

問題

https://atcoder.jp/contests/ttpc2019/tasks/ttpc2019_d

解法

各 X_i は何回か (0 回かもしれない) 2 個ずつ取ることができる．X_i を最大何回まで 2 ずつ引いていくことができるかをまず調べる．この回数 + 1 だけ各山に石があると問題を置き換えると，ニムの必勝法を適用できる．O(N + sqrt(10^6))．

解答

https://atcoder.jp/contests/ttpc2019/submissions/7220125