好き！
確かに天才系問題だけど、実験を積み上げると見えて来る感じが最高！！！

問題概要

$H$ × $W$ の盤面に何個かのコマが置かれている。先手と後手が交互に、以下のいずれかの動作を繰り返す:

コマを 1 つ選び、それを 1 マス左か下に動かす (ただし移動先のマスにコマがあってはならない)
コマを 1 つ選び、盤面から取り除く

先に操作を行えなくなった方の負けである。双方最善を尽くしたとき、どちらが勝つか？

制約

$1 \le H, W \le 200$

考えたこと

こういうのは小さいケースから試して行くと良さそう。

コマが 0 個のとき

自明に負け盤面である (終局状態)

コマが 1 個のとき

それを取り除けば相手に負け盤面を渡せるので、勝ち

コマが 2 個のとき

先にコマを取り除くしかなくなった方が負けることになる (コマを取り除いた瞬間、勝ち盤面を相手に渡してしまうため)。

一方、コマを動かせなくなる状態というのは左下を (0, 0) として、

(0, 0) と (0, 1)
(0, 0) と (1, 0)

という状態にコマがなったときにそうなる。どちらにしても、それぞれのコマの (0, 0) からのマンハッタン距離を $a, b$ として $a + b - 1$ 手打つことになる。よって

$a + b$ が偶数のとき、勝ち
$a + b$ が奇数のとき、負け

となる。

コマが 3 個のとき

上の考察から、各コマの (0, 0) とのマンハッタン距離のパリティが重要になりそう。

偶数が 2 個で奇数が 1 個のとき、偶数コマを 1 個取り除けば「偶数 1 個と奇数 1 個」という負け盤面を相手に渡せるので勝ち
偶数が 1 個で奇数が 2 個のとき、奇数コマを 1 個取り除けばよくて同様に勝ち
奇数が 3 個のとき、取り除いても「奇数 2 個」という勝ちを相手に渡してしまうし、動かしても「偶数 1 個と奇数 2 個」という勝ちを相手に渡してしまうし、負け
偶数 3 個も同様にして負け。

コマが 4 個のとき

この調子で考察を進めると、やがて「初期盤面で (0, 0) とのマンハッタン距離が偶数のコマ数と奇数のコマ数」による特徴づけが出てきそう。もう少し頑張ってみる。

奇数 4 個：勝ち
偶数 1 個と奇数 3 個：勝ち
偶数 3 個と奇数 1 個：勝ち
偶数 4 個：勝ち

なのはすぐに見える。いずれも盤面から取り除くことで「偶数 3 個」または「奇数 3 個」を相手に渡せる。ここから

偶数 2 個と奇数 2 個：負け

もわかる。

この調子で

この調子で整理していくと、初期盤面で偶数 $a$ 個、奇数 $b$ 個として、

$a - b$ が 3 の倍数のときは負け
それ以外は勝ち

であることが見て取れる。理由は簡単で、

「○」になっているマスはいずれも「取り除く」という操作のみで「×」に遷移できる (取り除く操作は下図表の「上」か「左」のマスへの移動を表す)
「×」になっているマスからは「取り除く」をしても「(移動できるコマがあったとして) 移動」をしても、からなず「○」に移動してしまう

ということからわかる。

なお実装上は、こちらが「後手」であることに注意。つまり、勝敗が逆転する。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int H, W; cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    reverse(fi.begin(), fi.end());

    int a = 0, b = 0;
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (fi[i][j] == 'o') {
                if ( (i + j) % 2 == 0 ) ++a;
                else ++b;
            }
        }
    }
    if ( (a - b) % 3 == 0 ) cout << "YES" << endl;
    else cout << "NO" << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

yukicoder No.819 Enjapma game