グランディ数の問題の解き方メモ (ARC072 D - Alice&Brown)

あまりに苦手なので、やまさん(@yamasangamasan)に解き方のコツを聞いたのでメモしました。文章だらけなのでかなり読みづらいです...
グランディ数を使う問題は、
二人零和有限確定完全情報ゲームです(!)

AとBの２人がいて、ある操作行うようなゲームをします。お互いが最適な行動をしたときに、どちらが勝つか判定してください。
今回は以下の問題を例として使って行きます。
ARC072 D - Alice&Brown
$X$ と $Y$ は、便宜上 $X \leqq Y$ としておきます。

基本方針
小さいケースのグランディ数を求める
帰納法で示す
規則性の見つけ方
終わりに
参考文献

基本方針

操作ができずに負けが決まる状態をグランディ数が0であるとし、小さいケースについてのグランディ数を求めていく
後で詳しく述べます。
先にグランディ数を簡単に説明すると、0のときは後手が勝ち、それ以外だと先手が勝ちになるようなものです(逆もあります)。
グランディ数が0になるパターンとならないパターンの規則性に目星をつける
ある条件を満たすとグランディ数が0に、満たさない時には0以外になる、というような規則性を探します。
先ほどの規則性によって求められる数が、実際に正しいグランディ数であることを証明する
これは、2つのことを証明します。
ある状態においてグランディ数が0であったときに、そこから1回操作をすると起こり得る全ての状態(以降は遷移先と表現します)についてグランディ数が0となるものが存在しないこと(もちろん、遷移先が必ず0以外になる、ということと同じです)
ということと、
ある状態においてグランディ数が0でないときに、遷移先にグランディ数が0となるものが少なくとも1つは存在すること
の2つです。これは、帰納法を用いて証明することができます。

小さいケースのグランディ数を求める

ある状態 $S$ についてのグランディ数を求めます。

$S$ のとき、なにも操作ができない状態ならばグランディ数が0となります。
それ以外の場合、 $S$ の遷移先のうちどれか1つの状態を $S'$ としたときに、あり得る全ての $S'$ についてのグランディ数を求め、 $S'$ に存在しない数のなかで最小の非負整数となります。

今回の問題において、ありうる $X,Y$ の状態を $(X,Y)$ という表記をすると、
(0,0), (0,1), (1,1)はこれ以上遷移ができないのでグランディ数は0です。
(0,2)は(0,1)に遷移できます。(0,1)はグランディ数が0なので(0,2)のグランディ数は1になります。
(1,2)は(0,2)に遷移できます。(0,2)はグランディ数が1なので(1,2)のグランディ数は0になります。
(0,4)は(0,2)と(1,2)に遷移できます。この2つのグランディ数はそれぞれ0と1なので、(0,4)のグランディ数は2になります。

そして、グランディ数が0のときは後手の勝ち、それ以外のときは先手の勝ちとなります。
グランディ数が0のときは、必ず0以外の状態に遷移するしかなく、またグランディ数が0以外のときは必ず0となるような遷移が存在します。
なので、グランディ数が0でないような状態で自分のターンが回ってきたとき、グランディ数が0となるように操作をしてから相手にターンを回せば、必ず勝つことができます。

こうして求めたグランディ数について、どのような場合に0、どのような場合に0以外になるか、規則性を見つけます。
今回の問題における規則性は、
$|X-Y|\leqq 1$ ならばグランディ数は0、それ以外なら0以外
という規則です。規則の見つけ方については、最後に簡単に述べますが、基本的には経験と発想力で見つけるしかないかと思います…

帰納法で示す

数学的帰納法で、2つのことを証明します。
ある状態 $S$ において、規則性を適用して求めたグランディ数を $g(S)$ とします。この $g(S)$ が実際のグランディ数と一致することは、以下の二つを示すことができればよいです。

ある状態 $S$ において $g(S)=0$ であったときに、任意の遷移先 $S'$ について $g(S') \neq 0$ であること(もしくは遷移先が存在しないこと)
ある状態 $S$ において $g(S)\neq 0$ のときに、遷移先 $S'$ に $g(S')=0$ となるものが少なくとも1つは存在すること

です。この2つを示すことができれば、 $g(S)$ は正しくグランディ数を求められていることになります。
今回用いる帰納法についての軽いおさらいです。ある自然数 $n$ に関する事柄(今回は上記の2つのことです)が成り立つことを、

$n=1$ の場合に成り立つ
$n=k$ のとき(もしくは $n \leqq k$ のときに成り立つとき)に、 $n=k+1$ で成り立つ

の2つのパートに分けて証明します。
これを組み合わせると、 $n=1$ で成り立つので $n=2$ で成り立ち、 $n=1$ (と $n=2$ )で成り立つので $n=3$ で成り立ち…と全ての $n$ について成り立つことができます。

帰納法を用いてどうやって証明するかというと、まずは全ての状態をグループ分けしていきます。そのときに番号を割り振り、 $n$ を決めていきます。
今回は、 $n = X+Y$ とします。(0,0)は $n=0$ 、(0,2)と(1,1)が $n=2$ 、といった具合です。
ここで、 $n$ の決め方で注意するべきポイントが存在します。

ある状態において $n=k$ だったとき、その遷移先では $n$ は $k$ 未満であること

です。でないと、証明の際にループをしてしまい証明できなくなります。
例えば、 $n=max(X,Y)$ のように定義をしてしまうと、(2,2)の遷移先に(0,3)が存在するため、 $n=2$ の遷移先に $n=3$ が存在することになってしまいます。これでは証明ができません。
規則性を探す実験の段階で、この $n$ についても気を配りつつ探していくといいでしょう。
ということで上記のことに気を付けながら $n$ を定義していきます。
ということで、定義した $n$ をもとにして、見つけた規則がグランディ数を求めることができていることを証明していきます。
規則性を振り返ってみます。

$|X-Y|\leqq 1$ ならばグランディ数は0、それ以外なら0以外

です。これを適用して求めた数が、

ある状態 $S$ において $g(S)=0$ であったときに、任意の遷移先 $S'$ について $g(S') \neq 0$ であること(もしくは遷移先が存在しないこと) 　　
ある状態 $S$ において $g(S)\neq 0$ のときに、遷移先 $S'$ に $g(S')=0$ となるものが少なくとも1つは存在すること

という2つの条件を満たしていくことを示していきます。

$n=1$ の場合に成り立つ
$n=1$ とは限らず、小さい数ケースについて成り立つ、でも大丈夫です。
小さいケースは最初に実験をしていれば、その規則が実験結果と等しくなっていることで証明になります。
今回は、 $n=0,1,2$ についてまとめて証明します。

[1]. $n=0$
(0,0)のみです。 $g(S)=0$ です。遷移先が存在していないのでこれは条件を満たします。

[2]. $n=1$
(0,1)のみです。 $g(S)=0$ です。これも遷移先が存在しません。

[3]. $n=2$
(1,1)および(0,2)です。前者は $g(S)=0$ 、後者は $g(S) \neq 0$ です。(1,1)は遷移先が存在しません。(0,2)の遷移先には(0,1)があり、これは $g(S')=0$ なので条件を満たします( $X$ と $Y$ は、便宜上 $X \leqq Y$ としていたので、本来なら(1,0)に遷移をするのですが(0,1)と表記しています)。

ということで、 $n=0,1,2$ の場合は条件を満たしていることがわかりました。

$n=k$ のとき(もしくは $n\leqq k$ のときに成り立つとき)に、 $n=k+1$ で成り立つ
ここがふんばりどころになります。うまく $n\leqq k$ の条件を利用できるようにして当てはめていきます。今回はあまりこの条件は必要ないですが…
$k+1 \geqq 3$ の場合についてのみこれが示せればいいです(0,1,2は証明済みのためです)。
このとき、 $X,Y$ のうちどちらか片方はすくなくとも2より大きく、必ず操作ができます。
$X\leqq Y$ という条件をたてていたので、 $Y$ を操作することを考えていきます。
$X=Y$ 、 $X+1=Y$ 、 $X+1 \lt Y$ の3つのパターンに分けることができます。最初の二つは、 $g(S)=0$ で、最後のパターンのみ $g(S) \neq 0$ です。
$X=Y$ のとき
$Y$ から $p$ だけ減らし、 $X$ にその半分を追加するとします。
このとき、 $(Y-p, X+\frac{p}{2})$ となります。
$X=Y$ であることから、 $(X+\frac{p}{2}) - (Y-p) = \frac{3p}{2}$ となり、 $p \geqq 2$ であることから、3以上の差が生まれます。ということで、遷移先は $X$ と $Y$ の差が必ず1より大きいので、 $g(S') \neq 0$ です。
$X+1=Y$ のとき
上と同じことを考えます。
$Y$ から $p$ だけ減らし、 $X$ にその半分を追加するとします。
このとき、 $(Y-p, X+\frac{p}{2})$ となります。
この差は、 $(X+\frac{p}{2}) - (Y-p) = \frac{3p}{2}-1$ となり、差は2以上です。
よって、 $g(S') \neq 0$ です。
$X+1 \lt Y$ のとき
$Y$ から $p$ だけ減らし、 $X$ にその半分を追加するとします。すると、差は次のようになります。
$(Y-p) - (X+\frac{p}{2}) = Y-X-\frac{3p}{2}$
$|Y-X-\frac{3p}{2}|\leqq1$ となるように $p$ を決めます。
$p=\frac{(Y-X+1)}{3}×2$ とすると、遷移先の $X,Y$ の差が1以下になり、 $g(S')=0$ になります。

ということで、全ての $X,Y$ のペアにたいして、 $n=k+1$ のときに条件を満たすことがわかりました。
ので、

$|X-Y|\leqq 1$ ならばグランディ数は0、それ以外なら0以外

という規則はめでたくグランディ数を求めていることになりました。
あとは、これをもとに答えを出力していけば答えとなります。

規則性の見つけ方

グランディ数の規則性の見つけ方は、経験によるものが多いです(やまさん談)。
問題の操作でどんなことをするかによって、ある程度目星をつけることができるみたいです。
一例を以下に示します。もちろん例外もありますので、頭の片隅に入れておく程度がいいかと思います。あくまで経験による感覚的なものですので、違っている場合もあります。ご了承ください。

2つの数字を操作するパターン
今回の問題のパターンです。このパターンの場合、
2つの数字を式で表した結果が規則になっている場合が多い
みたいです。特に、
操作において、片方で減算してもう片方で加算、のような操作をすると2つの数字を加算、もしくは減算した式が規則になることが多いそうです。
もし操作が、掛け算や割り算だった場合は、規則に掛け算や割り算、余りなどが絡むことが多いそうです。
文字列を扱うパターン
1文字ずつ減らしていく操作ならば、文字列の長さの偶奇が基本的に絡んできます。
終了条件が多いパターン
終了条件だけをみて、何かしらの規則が見つかることが多いです。

おそらくこれだけでなく、膨大な量のパターンがあると思います。経験していくしかなさそうです…
あとは、この問題に限ったことではないですが、小さいケースにコーナーケースが潜んでいることがありますので注意をしましょう…
これらをもとにして、問題の時間制限内に答えを見つけられるような計算量の規則を探していけば、この手の問題に答えることができるようになります(といいですね！)。

終わりに

グランディ数は個人的にあまり見かけない問題ではありますが、解けるようにしておくとだいぶ変わってくるかなと思っているので、このメモをもとに自分も解けるようにしていきたいですね…

参考文献

グランディ数 - zukky162のブログ

ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。