AtCoder Regular Contest 012

更新日時:

AtCoder Regular Contest 012

ソースコード

解法のメモ

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;
            }

である。

D - Don’t worry. Be Together

ポイント

その他