さかなのきもち

競技プログラミングの話が主になるかもしれません

yukicoder contest 211 E - Enjapma game 解説

感想

見つけたときにびっくりしたので出題してみました。
皆さんがどんな風に考えたのか気になるな~

解説

盤面がチェス盤のように、白と黒の市松模様で塗られているとします(このとき、一番左下を白としてください)。
結論を述べると、以下の条件が成り立つとき、盤面は負け盤面です。

条件:白いマスに置かれた駒の数+黒いマスに置かれた駒の数*2が3の倍数となる

これから、この事実を証明しましょう。説明のため、条件の太字部分をグリッド数と呼ぶことにします。

1.終了盤面が負け盤面である
終了盤面は駒がありませんから、これは自明です。

2.負け盤面から負け盤面へは遷移できない
今、負け盤面ですからグリッド数は3の倍数です。手番に出来る操作は次の4通りです。
 a.白いマスの駒を取り除く。
   ⇒グリッド数は1減少
 b.黒いマスの駒を取り除く。
   ⇒グリッド数は2減少
 c.白いマスの駒を黒いマスへ移動させる(白いマスと白いマスは隣り合っていないことに注意してください)
   ⇒グリッド数は1増加
 d.黒いマスの駒を白いマスへ移動させる
   ⇒グリッド数は1減少
と、上で見た4通りいずれの場合でも、グリッド数が3の倍数になりません。
よって、負け盤面から負け盤面へ遷移できないことが証明できました。

3.勝ち盤面からは負け盤面へ必ず遷移できる
今、勝ち盤面なのでグリッド数は3の倍数ではありません。状況を以下のように場合分けします。
 a.駒が1つしかない場合
   その駒を取り除けば負け盤面になります。
 b.グリッド数が3で割ると1余り、白いマスに駒がある場合
   白いマスの駒を取り除けば良いです。
 c.グリッド数が3で割ると1余り、白いマスに駒がない場合
   黒いマスの駒を白いマスへ移動させれば良いです。
 d.グリッド数が3で割ると2余り、黒いマスに駒がある場合
   黒いマスの駒を取り除けば良いです。
 e.グリッド数が3で割ると2余り、黒いマスに駒が無い場合
   白いマスの駒を黒いマスへ移動させれば良いです。
   (a.より、駒が複数ある、つまり一番左下以外のマスに駒があることが保証されてることに注意してください。)
と、上でみた5通りいずれの場合でも、グリッド数を3の倍数にすることができます。
よって、勝ち盤面からは負け盤面へ遷移できることが証明できました。

おまけ

手番に出来る行動が、「駒を取り除く」か「駒を1つ下のマスに動かす(移動先に駒がある場合は無理)」だった場合、勝敗の判定条件はどうなるでしょう?
分かった人はコメントしてみてください