No.819 Enjapma game - yukicoder
writerさんの解法が天才なので、地道に実験して解いた私の解法もまとめてみたいと思います。
解法
「その盤面状態で自分のターンが回ってきた時に勝つ/負ける」という状態をそれぞれ勝ち状態/負け状態と呼ぶことにします。
駒の数が少ないほうから考えていきましょう。
駒が0個
操作できる駒がないので負け状態です。
駒が1個
その駒を取り除くことで駒0個の負け状態を相手に押し付けることができるので、これは勝ち状態です。
駒が2個
ここから少し考えることが増えます。
駒を取り除いてしまうと駒1個の勝ち状態を相手に与えてしまうので、2人は駒を動かすほうの操作をしたいです。いずれ動かせる駒が無くなって詰むわけですが、その盤面はどちらのプレイヤーが引いてしまうでしょうか。
駒の具体的な位置を考えてしまうと問題がとても複雑になるので、盤面を特徴づける何らかの便利な数を見つけたいです。このように「駒を隣に動かす」という操作をする問題の多くで有効なのが偶奇で、盤面を市松模様のように「左下からの距離が偶数か奇数か」で塗り分けます。そして「 個の駒のうち
個が偶数マスにある」という状態を
と特徴付けると、1つの駒を隣に動かす操作では
の値が1増加または減少します。
駒が2個の場合、動かせる駒がないときには必ず2つの駒は隣り合っているのでその偶奇は異なり、すなわちこれは 状態です。そうすると、
の盤面からは必ず相手に
の状態を押し付けることができて、
状態を押し付けられ続けて動かせる駒が無くなったプレイヤーが負けます。
駒が3個～4個
先ほど説明した状態 を利用して勝ち負けを考えていきます。ここで以下のような「パスカルの三角形」に似た図を用意します。
この図において、プレイヤーの操作は
- 駒を取る：斜め上の状態を相手に与える。
- 駒を動かす：隣の状態を相手に与える。常に行えるとは限らない。
と考えることができます。
そうすると、この表の埋め方として
- 斜め上のどちらかに負け状態がある場合、それは勝ち状態である。
- 斜め上と隣が全て勝ち状態であることが確定している場合、それは負け状態である。
というルールを作ることができます。これで駒4個までの状態は埋まります。
駒が5個～
駒が5個の場合を考えます。先ほどのルールで以下の図の状態までは埋まるのですが、両端はどうなるでしょうか。
上側も内側も勝ち状態に囲まれているので、プレイヤーは可能な限りこの2マスを往復して押し付け合います。そのままいずれ駒が詰まった状態になって動かせなくなりますが…果たしてそのようなことはあるでしょうか？
ここで駒の偶奇の「偏り」に注目します。この図において両端に近いところは、駒が偶数マスと奇数マスの片方に極端に寄っていることを示しています。対して駒が詰まって動かせない状態というのは、直感的には偶数マスの駒と奇数マスの駒はだいたい同じくらいありそうです。
駒が詰まった状態で最大でいくつまで差が出る可能性があるか…というのを具体的に求める必要はありませんが、「駒の数が5個以上で、駒が詰まった状態で、偶数マスあるいは奇数マスの駒の個数が0～1個」という盤面は実際に並べてみるとあり得ないことが分かります。
ということは駒を取り除かずに動かし続ける限りは、必然的に内側のほうに遷移していくことになります。そのため両端の2マスのうち内側はいずれ勝ち状態を相手に渡してしまうので負け状態で、それを相手に押し付けられる外側が勝ち状態です。
こうして新しいルールを作ることができます。
- 駒5個以上の段において左右の端に未確定マスが横に2つ並び、勝ち状態に囲まれている場合、内側が負け状態で外側が勝ち状態である。
このルールにより、駒が6個以上の場合に対しても全ての状態を埋められるようになります。
Eで実験した何か pic.twitter.com/jCi4OvsVfG
— アルメリア (@armeria_betrue) April 19, 2019
あとは初期状態がどちらの状態かを判定すればよいです。図の規則性から3で割った余りで判定できるので、適切に式を立てて答えを出しましょう。例えば中心との距離を見ると偶数段/奇数段それぞれで共通の構成になっているので、私のコードはそれで判定しています。
「国王が先攻であるときにあなたが勝てるか」なので、初期状態が負け状態のときに YES を出力することに注意です。
