AOJ 3057 - First Kiss (RUPC2019 Day2 G)
解法
まずは、キッポーが1本のときについて考えます。
この問題についてのグランディ数を求めることができれば、あとは本のキッポーについてのグランディ数のxorを取った結果を見ればよいです。
キッポーの長さを0にした方が負けなので、1だけ残して相手のターンにまわすことができれば勝つことができます。
ということで、長さが1の際を最終地点として考えていきます。
基本的に、の長さだけ1ターンで食べることができますので、
の長さで自分のターンになれば、長さを1にして相手のターンに回すことができます。
逆に、現在の長さがのときは、
の任意の長さにすることができます。
これを踏まえると、長さがのときのグランディ数は、
となります。
これが0なら後手の勝ち、そうでなければ先手の勝ちです。
あとは、本のキッポーについて、先ほどの式でグランディ数を計算し、xorをとっていけば、1本の際と同様の判定で勝者を調べることができます。
感想
小学生かそこらのころ、0からスタートして、交互に1~3加えた数字を言っていき、21だか23になったら負け、というゲームをしたことがあります。
確か何かの新聞の広告で、このゲームについての必勝法を考えよう！みたいな問題が載っており、似たようなことを考えました(グランディ数とかそういうのは知らないので、どの数字を言ったら確実に負けてしまうのか、とかそういったあいまいな話ですが)。
グランディ数の問題にしては割とシンプルなため、珍しく自力で解くことができました。うれしいです。
ちなみに、この記事を全て書き終えてから、キッポーがポッキーになっていたことに気づいて慌てて直したのは秘密です。
