ARC 072 D Alice & Blown

所見

解説見ると明らかに結論ありきの証明で笑ってしまう

問題概要

2つの山があり、それぞれX個とY個の石が置いてある。イカの操作を先手後手が交互に行っていき、先に操作ができなくなった方が負けの時、先手後手のどちらが勝つかを求めよ。
- 片方の山から 2i個の石を取り、そのうち i個の石を捨て、残りのi個の石をもう片方の山に置く。ここで、整数iの値は山に十分な個数の石がある範囲で自由に選ぶことができる。

取った方針

bo[l][r] := その盤面のgrundy数とすると、各盤面のgrundy数はメモ化再帰で求めることができる。(O(N²))X,Y <= 10¹⁸なのでgrundy数を求めては到底間に合わないが、X,Y = 100 くらいで試すと明らかに

 abs(X - Y) <= 1

の時grundy数が0になっているので、証明なしで投げると通る。

正しい方針

AtCoderの解説、一行目に結論が書いてあって二行目以降に証明が書いてあるだけなんですけど(絶望)

得られた知見

• 二人なんとかかんとか有限なんとかゲームはgrundy数というのを計算してみると何かが見えたり見えなかったりする
  • grundy数は盤面ゲームの盤面にいい感じに名前を付けるための数だという理解
  • 終状態を0として、grundy数がnの状態からはn未満の任意の状態に遷移できる。

解くのに必要な要素

• grundy数

周辺調査によって得られた知見

特になし