yukicoder No.819 Enjapma game

ゲーム問題にしては面白い(といっても典型だと思う)問題だったので。

問題概要

H×Wのグリッドに駒がいくつか置かれている。相手スタートで以下の操作を交互に繰り返す。

• 駒を1つ選んで取り除く。
• 駒を1つ選んで、左か下のどちらか隣のマスに移動させる。ただし、移動先に他の駒があってはならない。

操作を行えなくなった方の負け、というルールで、お互いに最善手を取ったとき勝てるか判定せよ。

No.819 Enjapma game - yukicoder

解説

ゲーム分野にはいくつか解法があって、大体そのどれかに該当する。

• DFSを行って最善手を全探索するタイプ(grundy数が使えない場合はこっち)
• grundy数を用いるタイプ(上のよりシンプルな問題で用いることが出来る)
• その他数学的な考察を行うことで規則的に問題を解くタイプ

今回は上2つをやろうとすると探索範囲が広すぎて計算が間に合わない。ということで自然と規則を見つけて解く形に。

3x3辺りまで適当に脳内シミュレーション・grundy数の設定を行っていると、「盤面を一松模様と捉えて、移動=白黒を1つひっくり返す」と捉えるとよさそうなことに気が付きます。主に駒が2個の時に勝利条件=白黒1つずつだったので。
これは、最終的に駒を1つ取り除いたほうがその次に相手が最後の駒を取り除いてくるので負けるため、お互い可能な限り移動し続けます。その結果必ず白黒1つずつの状態になって移動できなくなるので、それと同じ状態(白黒→白黒の遷移は出来ないけど、必ず白白→白黒と黒黒→白黒は存在するので)で負けることが分かります。

さて、市松模様の白黒を用い始めたところで、駒の個数ごとに勝てる条件を探してみましょう。探し方は「2個の基準が存在するので、3個以降はn-1個の時の勝利条件を相手が作れない」状態を探すことです。

• 1個→相手が取り除くので必ず負けます
• 2個→前述の通り白黒1つずつで勝ち
• 3個→白白白と黒黒黒で勝てます(色を変えてきても取り除いてきても白黒の状況が作れます)
• 4個→白白黒黒で勝てます(同様相手の行動に応じて必ず白白白か黒黒黒が作れます。それ以外は逆に白白白か黒黒黒を作られます)
• 5個→白白白白黒か白黒黒黒黒が勝利条件です
• 6個→白×6、白×3黒×3、黒×6が勝利条件です

という感じです。これを見直して規則を探すと、「白の個数-黒の個数が3の倍数で勝利」という規則が見えてくるのではないでしょうか。

ということで、これをそのまま実装すると通ります。O(HW)。

int main() {
    int h, w;  cin >> h >> w;
    vector<string> s(h);  cin >> s;
    int cnt = 0;
    rep(i, h)   rep(j, w) {
        if (s[i][j] == 'o') cnt += ((i + j) & 1 ? 1 : -1);
    }
    cout << (cnt % 3 == 0 ? "YES" : "NO") << endl;
    return 0;
}

感想

僕がゲーム分野得意なのって、絶対にこの解き方で解けるからなんだよね…あまりいいことではない気がする…