naiの日記

ソフトウェアエンジニアから放射線科診断医にジョブチェンジしました。趣味のことを書きます。

Google Code Jam 2019 Round3

GCJ 2019 Round3 に参加。結果はAだけ解けて332位でした。

f:id:nai_62:20190609083219p:plain

A. Zillionim

問題概要

1012枚のコインが一列に並んでいます。先手と後手で交互に、連続した1010枚のコインを取っていきます。ただし間が空いている場合連続しているとはみなされません。コインを取れなくなったら負けです。

あなたは後手です。先手は毎ターン、可能な全ての取り方から一様ランダムにコインの取り方を選びます。99.8%以上勝利しよう。

解法1

C=10^ {10} とおきます。連続したコインの区間をセグメントと呼ぶことにします。また、長さ L のセグメントのランク \lfloor L / C \rfloor で定めます。

ランク r のセグメントがあったとき、左から kC 枚残すようにコインを取ればランク k とランク r-1-k のセグメント2つができます。また、左から kC+C-1 枚残すように取れば、だいたいランク k とランク r-2-k のセグメント2つができます(Cは十分大きいので、境界条件を無視しています)。

よって、ランク r のセグメントのGrundy数を G _ r と書くことにすると、ランク r のセグメントからコインを取ることによって遷移できる状態のGrundy数は、

G _ {k} \; xor \; G _ {r-1-k} \; (0 \le k \le r-1)

または

G _ {k} \; xor \; G _ {r-2-k} \; (0 \le k \le r-2)

となることがわかります(セグメントが2つに分割する場合、Grundy数は単にそれらのxorを取るだけなので)。あとはこれをもとに、ランク0~100の各状態に対してGrundy数を前計算しておき、NimをすればOK。

解法2

後で聞いた話によると、序盤に長さ 2C のセグメントを沢山作ることで、事実上自分だけに決定権がある状況を作り出せるため、こんなことをしなくてもほぼ勝てるようです。天才

コメント

解法1を思いつくのに時間がかかったうえ、インタラクティブでどはまりしてしまい、この問題だけでほとんどの時間を費やし、後は何もできずに終了しました。つらい。

とはいえどの道Stage Finalに行くのは無理ですし、人生初のGCJ Round3だったのでいい記念になりました。Aを通せて良かった。