AtCoder Regular Contest 012 - C - 五目並べチェッカー を解きました

AtCoder Regular Contest 012 - C - 五目並べチェッカーを解いてみました。

五目並べの「ある配置」が与えられるので、ありうる配置なのかどうかを答える問題。ありえない配置は、

• どちらかが勝っているのに、もう片方が石を置いている
• 石の数がおかしい

のどちらかです。先攻は黒で、マスは19x19です。

例を見てみると、例6が一番ネックになりそう。黒10個が1列にあって、白がバラバラのところに9個ある。この場合、黒が最後の1手を打って終わっているように見えるけど、どう頑張ってもそれ以前に黒が勝っていることが確定している。なので、これは「ありえない状態」と判定しないといけない。

こうしためんどうなケースがいっぱいありそうなので、最後の石の配置を見るだけで「ありうるかありえないか」を判定する条件を書くのは難しそうだし、書いたとしても泥沼にはまりそう。「勝者が決まってるのにもう片方が石を置いている」の判定をどうにかしないといけない。

なので、考え方を少し変えます。結局、どちらかが勝った局面では、どこかの石が最後の1手になっているはず。つまり、今ある石のどれかを排除して「どちらも勝っていない」という状況になっているかどうかを調べればよさそう。

これを踏まえて考えていきます。まず、石の配置を配列に入れながら、黒と白の石の数を数えます。

  ll cnt = 0;
  for (ll i = 0; i < 19; i++) {
    string S; cin >> S;
    for (ll j = 0; j < 19; j++) {
      if (S[j] == 'o') {
        cells[i][j] = 0;
        cnt++;
      } else if (S[j] == 'x') {
        cells[i][j] = 1;
        cnt--;
      }
    }
  }
  if (cnt > 1 || cnt < 0) {
    cout << "NO" << '\\n';
    return 0;
  }

黒と白の石の数は、黒が1個多いか、同じになるので、それ以外は「ありえない」と判断していい。

さらに、勝っている人と石の数の整合性を考えた判定も入れます。

  if (win(0) && win(1)) {
    cout << "NO" << '\\n';
    return 0;
  }
  if (win(0) && cnt == 0) {
    cout << "NO" << '\\n';
    return 0;
  }
  if (win(1) && cnt == 1) {
    cout << "NO" << '\\n';
    return 0;
  }

win(0)は黒が勝つこと、win(1)は白が勝つことを表す関数で、これは後で書くことにします。とりあえず、両者が勝ってることはありえないし、黒が勝って黒の個数が多くないのもありえない、白が勝って黒の個数が多いのもありえない。これらを除外します。

今後、石の配置を見て、勝っているかどうかを簡単に判定できた方がいいので、その処理も書きます。それぞれのマスを基準として、一方向に連続する5マスに同じ色の石が置かれているかどうかを調べる関数を作ります。

bool win(ll turn) {
  bool ans = false;
  for (ll i = 0; i < 19; i++) {
    for (ll j = 0; j < 19; j++) {
      for (ll k = 0; k < 5; k++) go[k] = {i + k, j};
      ans = (ans || is5(turn));
      for (ll k = 0; k < 5; k++) go[k] = {i, j + k};
      ans = (ans || is5(turn));
      for (ll k = 0; k < 5; k++) go[k] = {i + k, j + k};
      ans = (ans || is5(turn));
      for (ll k = 0; k < 5; k++) go[k] = {i + k, j - k};
      ans = (ans || is5(turn));
    }
  }
  return ans;
}

turnの人が勝っているかどうかをチェックします。goには、マスの位置情報を入れておきます。下5マス、右5マス、右下5マス、左下5マス、この4パターンについて、同じ色の石が置かれているかどうかを、is5という関数を使って調べます。この関数は次のように書きました。

bool is5(ll turn) {
  bool ans = true;
  for (ll k = 0; k < 5; k++) {
    ll gi = go[k].first, gj = go[k].second;
    if (0 <= gi && gi < 19 && 0 <= gj && gj < 19) {
      if (cells[gi][gj] != turn) ans = false;
    } else {
      ans = false;
    }
  }
  return ans;
}

5マスとも盤の中にあって、5マスとも対象の色の石が置かれていたら true を、それ以外の場合は false を返します。こうして、5マスそろっている箇所があるかどうかを調べ、1つでもあれば、winだと判定します。

さて、ここまでで、石の個数に矛盾があるかどうか、勝者と石の個数に矛盾があるかどうか、を調べてきました。あとは、「片方が勝ったのに、もう片方がまだ石を打っているか」を調べればいいです。

これは、先ほど書いたように、「ある1手が最終手だった」というケースであることを調べればよく、今ある配置から1手を戻したときに、勝者が確定していない状況にできるかどうかを調べればいいです。

  for (ll i = 0; i < 19; i++) {
    for (ll j = 0; j < 19; j++) {
      ll old = cells[i][j];
      cells[i][j] = -1;
      if (!win(0) && !win(1)) {
        cout << "YES" << '\\n';
        return 0;
      }
      cells[i][j] = old;
    }
  }

  cout << "NO" << '\\n';

1か所だけ何もない状態にして、黒も勝ってないし白も勝っていない、という状態があればOK、ないなら「勝者が決まった後も石を置いた」ことを表しているのでダメ。これでおしまいです（提出 #18989583 試行錯誤したときにできたゴミが残っています・・・）。