AtCoder Regular Contest 012
Updated:
Source codes
Solutions
A - 週末
ポイント
B - アキレスと亀
ポイント
C - 五目並べチェッカー
解答
まず盤面から直前の手番(以下単に手番と呼ぶ)を確定させる必要がある。黒石の数 $-$ 白石の数 $= 0, 1$ でなければその時点でおかしいから NO である。これが $1$ の時は黒の手番、 $0$ の時は白の手番である。
次に勝利条件判定を黒と白の両方に対して行う。「どちらも勝利」という場合は NO である。「どちらも勝利していない」は YES である。その他は「黒の手番かつ黒が勝つ」または「白の手番かつ白が勝つ」以外はこの時点で NO である。以下「黒の手番かつ黒が勝つ」の場合について述べる。この場合、直前に打たれた可能性のある黒石を全探索する。その黒石を置いていない盤面、つまり、「 1 手前の盤面」は「白の手番かつどちらも勝利していない」である必要がある。このような黒石の除き方が存在する場合は YES であり、そうでない場合は NO である。
実装の方針
const int C = 19; とする。 typedef vector<string> ban; とする。また、盤面を class Go{}; で用意した方がいい。あとその盤面の状態を記述するために enum class state{}; も用意した方がいい。具体的には以下のようにすれば良いだろう。
enum class state
{
black_win,
white_win,
black_even,
white_even,
error,
};
class Go
{
public:
ban B;
vector<int> cnt = vector<int>(2, 0);
Go() {}
Go(ban V) : B(V) {
// cnt の処理もする。
}
bool win(char c)
{
// 勝利判定をする。
}
state st()
{
int t = cnt[0] - cnt[1];
if (!(t == 0 || t == 1))
{
return state::error;
}
bool black_turn = (t == 1);
bool black_win = win('o');
bool white_win = win('x');
if (black_win && white_win)
{
return state::error;
}
else if (black_win)
{
if (black_turn)
{
return state::black_win;
}
else
{
return state::error;
}
}
else if (white_win)
{
if (!black_turn)
{
return state::white_win;
}
else
{
return state::error;
}
}
else
{
if (black_turn)
{
return state::black_even;
}
else
{
return state::white_even;
}
}
}
};
後は初期状態の ban B; を埋め込んだ Go I(B); に対して state I_state = I.st(); として、上記の通りに場合分けしながら Yes(); No(); を判定すれば良い。黒が勝っている場合は以下のようにする。
if (I_state == state::black_win)
{
for (auto i = 0; i < C; i++)
{
for (auto j = 0; j < C; j++)
{
if (B[i][j] == 'o')
{
ban V = B;
V[i][j] = '.';
Go before(V);
if (before.st() == state::white_even)
{
Yes();
}
}
}
}
No();
}
ポイント
私が間違えていたところは、 Go::win(); の判定である。
if (0 <= x && x < C && 0 <= y && y < C && B[x][y] != c)
{
ok = false;
break;
}
は、範囲外参照の場合は if の中に節に入らないので 間違いである。 配列外参照にまつわる if 節を書いた場合は全体を否定する。 これが教訓である。正しくは、
if (!(0 <= x && x < C && 0 <= y && y < C && B[x][y] == c))
{
ok = false;
break;
}
である。