AtCoder Regular Contest 012 C - 五目並べチェッカー

問題

 19×19の碁盤の状態を与えるので五目並べの盤面として正常かどうかを判定せよ。

解法

 盤面について先手後手それぞれが勝っているか(五目並んでいるか)を判定する関数を用意する。まず与えられた局面で先手後手それぞれについて勝っているかを判定し、次のように場合分けをする。

  • 先手後手両方とも勝っている

 正常でない

  • 先手後手両方とも勝っていない

 石の数が正常であるか確認するだけで良い

  • どちらかが勝っている

 勝っている方が最終手を着手し、最終手を着手する前はどちらも勝っていない状態であったはずである。したがって盤上にある勝った側の任意の石を一つ取り除いた盤面のうち、どれか一つはまだ勝ってない状況でなければならない。それを判定すればよい。

反省

 37分53秒でAC。最初は五目以上並んでいる成分の個数を数えればいいのかなどと思っていたが、交差する点に打って同時に2個以上五目が作れる場合があるのでこれは断念。いくらか考えたところでこの最終手を一手戻すという発想が出てきた。

 サイズが小さいのでどのようにしても解けそうな反面、実装が楽で場合分けが少ないようなものを考えないとバグが多くなりそうなので診療に考えなくてはならない問題だと感じた。

 問題とは関係のない話だけど、コンピュータ将棋でもこうやって個々の要素を問題化していったら最初の入り口として良いのではないかとか話されていた気がしますね。あれ? これはテスト駆動開発みたいなものか?

コード

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

bool isWin(vector<string> b, char c) {
    //cが勝っているかをチェック
    ll dx[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
    ll dy[] = { -1, -1, 0, 1, 1, 1, 0, -1 };

    auto isOK = [&](ll i, ll j, char c) {
        return (0 <= i && i < 19 && 0 <= j && j < 19 && b[i][j] == c);
    };

    for (ll i = 0; i < 19; i++) {
        for (ll j = 0; j < 19; j++) {
            if (b[i][j] != c) {
                continue;
            }
            for (ll k = 0; k < 8; k++) {
                ll num = 0;
                for (ll ni = i, nj = j; isOK(ni, nj, c); ni = ni + dy[k], nj = nj + dx[k]) {
                    num++;
                }

                if (num >= 5) {
                    return true;
                }
            }
        }
    }

    return false;
}

bool solve(vector<string> b) {
    //石の数のチェック
    vector<ll> all_num(2, 0);
    for (ll i = 0; i < 19; i++) {
        for (ll j = 0; j < 19; j++) {
            if (b[i][j] == 'o') {
                all_num[0]++;
            } else if (b[i][j] == 'x') {
                all_num[1]++;
            }
        }
    }

    vector<bool> win(2, false);
    win[0] = isWin(b, 'o');
    win[1] = isWin(b, 'x');

    if (win[0] && win[1]) {
        //両方勝っていたらおかしい
        return false;
    } else if (win[0]) {
        //先手勝ち
        //先手が打った瞬間でないといけないので
        if (all_num[0] != all_num[1] + 1) {
            return false;
        }

        //最後に打った石を除いてみてすでに勝っていたらおかしい
        for (ll i = 0; i < 19; i++) {
            for (ll j = 0; j < 19; j++) {
                if (b[i][j] == 'o') {
                    //ここが最終手と仮定する
                    //1手戻す
                    b[i][j] = '.';

                    //判定
                    if (!isWin(b, 'o')) {
                        return true;
                    }

                    //盤の状態を戻す
                    b[i][j] = 'o';
                }
            }
        }
        return false;
    } else if (win[1]) {
        //後手勝ち
        //後手が打った瞬間でないといけないので
        if (all_num[0] != all_num[1]) {
            return false;
        }

        //最後に打った石を除いてすでに勝っていたらおかしい
        for (ll i = 0; i < 19; i++) {
            for (ll j = 0; j < 19; j++) {
                if (b[i][j] == 'x') {
                    //ここが最終手と仮定する
                    //1手戻す
                    b[i][j] = '.';

                    //判定
                    if (!isWin(b, 'x')) {
                        return true;
                    }

                    //盤の状態を戻す
                    b[i][j] = 'x';
                }
            }
        }
        return false;
    } else {
        //勝敗はついていないので数だけ
        return (all_num[0] == all_num[1] || all_num[0] == all_num[1] + 1);
    }
}

int main() {
    vector<string> b(19);
    for (ll i = 0; i < 19; i++) {
        cin >> b[i];
    }

    cout << (solve(b) ? "YES" : "NO") << endl;
}