SRM637D1M PathGame
snuke is sugoy
問題概要(原文)
$2$ 行 $W$ 列からなるグリッドを使って $2$ 人ゲームをする．グリッドには白マスと黒マスがある． 交互に各自のターンが来て，以下のことが行われる．
- 白マスを $1$ つ選んで黒マスにする．
常に「白いマスだけを辿って左端から右端までいける」必要がある．いけなくなるような操作をした方の負け． $2$ 人が最適に行動したときの勝者はどちらか？
考察
$W$ が $3$ 以下の場合は愚直にやれば解ける．
以下 $W \geq 4$ を仮定する． 両端 $2$ 列ずつに着目する．
左端側を $L$，右端側を $R$ と呼ぶことにする． $L$ と $R$ の両方に $1$ つ以上黒マスがあるとき，図のように最終的な始点と終点が定まる．
 |
|---|
重要な性質として，始点と終点が定まれば最終的に残っているマスの数の偶奇が定まるというのがある．なので，全てのマスから既に黒く塗られたマスを差し引いてやって，奇数回だけ手番が回ってくるなら先手の勝ち，そうでなければ後手の勝ち．
次に $L$ と $R$ のどちらかにだけ $1$ つ以上黒マスがあるときを考える． このとき，手番のプレイヤーは以下の図のように $1$ 列目を塗るか，$2$ 列目を塗るかで最終的な手番の数の偶奇を変更できる．よって先手の勝ち．
 |
|---|
最後に $L$ にも $R$ にも黒マスがないときを考える．このとき，先に黒く塗ってしまうと，必ず負けてしまうので，内側のマスたちのみに着目してゲームを行ったときの勝敗がそのままこのゲームの勝敗になる．よって再帰的に内側のマスたちに着目したときのゲームの勝敗を調べればいい．
 |
|---|
このようにして再帰的にゲームの勝敗を調べればよい．
ソースコード
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using Debug = System.Diagnostics.Debug;
using StringBuilder = System.Text.StringBuilder;
public class PathGame
{
public string judge(string[] board)
{
return f(0, board[0].Length - 1, board) ? "Snuke" : "Sothe";
}
public bool g(char[] a, char[] b)
{
var ok = new bool[2];
ok[0] = true; ok[1] = true;
for (int i = 0; i < a.Length; i++)
{
var next = new bool[2];
if (a[i] == '.') next[0] |= ok[0];
if (b[i] == '.') next[1] |= ok[1];
if (a[i] == '.' && b[i] == '.')
{
var x = next[0] | next[1];
next[0] |= x;
next[1] |= x;
}
ok = next;
}
if (ok.All(x => !x)) return true;
var win = false;
for (int i = 0; i < a.Length; i++)
{
if (a[i] == '.')
{
a[i] = '#';
if (!g(a, b)) win = true;
a[i] = '.';
}
if (b[i] == '.')
{
b[i] = '#';
if (!g(a, b)) win = true;
b[i] = '.';
}
}
return win;
}
public bool f(int l, int r, string[] board)
{
if (l > r) return false;
else if (r - l <= 2)
{
var a = board[0].Substring(l, r - l + 1);
var b = board[1].Substring(l, r - l + 1);
return g(a.ToCharArray(), b.ToCharArray());
}
else
{
var L = -1;
var R = -1;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
{
if (board[j][l + i] == '#') L = j;
if (board[j][r - i] == '#') R = j;
}
if (L == -1 && R == -1) return f(l + 2, r - 2, board);
else if (L == -1 || R == -1) return true;
else
{
var all = 0;
for (int i = l; i <= r; i++)
for (int j = 0; j < 2; j++)
if (board[j][i] == '.') all++;
var t = r - l + 1;
if (L != R) t++;
all %= 2;
t %= 2;
return all != t;
}
}
}
}
コメント
- $2$ 人ゲームだったら打てる手番の数の偶奇に着目するのはよくあるテクなので気をつけたい
- 今回の場合は「最終的に残るマスの数の偶奇が始点と終点を決めると定まる」というのが本質
