AtCoder Regular Contest 072 D. Alice&Brown

すんなり解けた割に納得がいかなかった。今日結構500点問題色々見たけど、安定しないなあと思うし本当によくこれで赤色目指すみたいな気持ちでいれましたねみたいな感じ。

問題文

読んで: D - Alice&Brown

解法

正直なんで解けたのか分かっていない。なんで解けたのかというのは、別に解法自体を理解していないということではなくて、解法を思いつくまでの考察の仕方が分からないという意味で、つまり今後同じ系統の問題が出題された場合にちゃんと考察を順に詰められる気がしない...

とりあえず考察するに当たってやったのは図示で、結局、変なベクトルを基底にした格子みたいなのを、一方向に好きなだけいけるので、ゴールに辿りついた人の勝ちみたいなイメージになる(下図)。

この時、書いた図がたまたまとても運が良くて、(4, 4)スタートだったのがかなり功を奏してる気がする、まぐれで解いてしまった。

一応ゲームの定石としてまあ「後手が先手を真似る奴」というのがあるわけですが、(4, 4)とかはまさにそのままになっていて、先手がここからどう動こうと、それとy=xで対称な動きを後手は必ず出来て勝てるなあという気持ちにはなった。

ちょっと一般化すると、a < bであるような(a, b)について、「a < i ∧ b ≧ 2i」でない限りは、先手が(a+i, b-2i)に動いたら、後手は(a-i, b-i)に出来て、y=xに平行に動ける。

で後は、(4, 4)スタートの場合はゴールは(0, 1)なわけですが、(0, 0), (1, 0), (1, 1)もゴールになりえて、かつこれらの内1つしかゴールにはなりえない(つまり例えば(0, 1)にも(1, 1)にも行けるという状態はありえない)ということも自明な考察としてした。

ここで問題になるのは、「a < i ∧ b ≧ 2i」が成り立つ時、例えば(0, 8)みたいなスタートでは、真似が出来ないだろという気持ちになったんですが、よくよく考えると(0, 8)からは(3, 2)に動けて、ここからはさっきと同じことになるなということに気づき、結論としては初めから|a-b| ≦ 1なら後手が勝つし、そうじゃなければ必ず初手で|a-b| ≦ 1になるように動かせるから先手が勝つという結論になって、まあ実際正しかった。

正直どういう風に考えればシステマチックに解けるのか分からん

追記:

grundy数見たら結構自明だね。便利。

00 00 01 01 02 02 03 03
00 00 00 01 02 02 03 03
01 00 00 00 01 01 04 03
01 01 00 00 00 01 02 02
02 02 01 00 00 00 01 01
02 02 01 01 00 00 00 01
03 03 04 02 01 00 00 00
03 03 03 02 01 01 00 00