ARC137 C - Distinct Numbers (600)
コンテスト中の考察
$ A_n < A_{n-1}となる様な操作をしたときに何らかの後手必勝の状態があればそれを選んで勝ち
そうでない場合、$ A_nを1ずつ減らす勝負になるので$ A_n-A_{n-1}が偶数ならアリス、奇数ならボブの勝ち
解説の解法
考察のそうでない場合については$ A_n = A_{n-1}+1とすればアリスの勝ちになる
元から$ A_n = A_{n-1}+1の場合、空いている最大の数に入れれば良い
そうしないと$ A_n > A_{n-1}+1な盤面を渡してしまうかも
これは$ Nと$ A_nの偶奇の違いによって勝敗が決まることになる
偶奇が一致するならアリス、違うならボブが勝つ