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

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

Educational Codeforces Round 73 E. Game With String (R2400)

面白かったけど場合分けが怖かった

問題へのリンク

問題概要

"...X......XX..X..X.XXX...X..."
のような '.' と 'X' からなる長さ  N の文字列が与えられる。

  • 先手は連続する  a 個の '.' をすべて 'X' に置き換える
  • 後手は連続する  b 個の '.' をすべて 'X' に置き換える

という操作を交互に行う。先に操作を行えなくなった方が負け。双方最善を尽くしたとき、どちらが勝つか?

ただし、 a \gt b であることが保証されているものとする。

制約

  •  1 \le (クエリ数) \le 3 \times 10^{5}
  •  1 \le N \le 3 \times 10^{5}
  •  (全クエリの N の総和) \le 3 \times 10^{5}

考えたこと

やはり  O(N) O(N\log{N}) くらいで解ければ OK。
すごくややこしいし、一見 Grundy っぽさ (盤面が本質的に分裂していくため) もあるのだけど、不公平ゲームだし Grundy はそのままでは扱いづらい。

ちょっとアドホックにいろいろ考えてみよう。少しわかってくるのは

  • 先手が初手何も打てなかったらどうしようもない
  • もし長さが  b 以上  a 未満の区間があったらその時点で先手はどうしようもない
  • 先手が手を打ったあとにもし長さが  2b 以上の区間があったらその時点で先手はどうしようもない (後手が必ず長さ  b区間を作れるため)

ということがわかる。よって解法としては、長さ  b 以上  a 未満の区間がないことを確認した上で、長さ  a 以上の区間 ( M 個とする) の長さを抜き出してきて、

  • 空だったらアウト
  • その中に長さ  2b 以上の区間が 2 個以上あったらアウト
  • 長さ  2b 以上の区間が 1 個含むときは、なんとかそれを解体しなければならない (後述)
  • 長さ  2b 以上の区間がなければ、 M が奇数個なら先手勝ち、偶数個なら後手勝ちになる。

長さ  2b 以上の区間が 1 個だけ含まれるとき

ここの場合分けはあまりにもしんどいので、こういうときは探索に頼ってしまってよいと思う!!!!!!!探索量は  N でおさえられるので、 O(N) で済む。

すなわち、長さ  2b 以上の区間に対して長さ  a区間をどのように置くかを全探索する。各場合について

  • もし長さ  2b 以上の区間が再び生じたらダメ
  • もし長さ  b 以上  a 未満の区間が生じたらダメ
  • そうでなければ、分割後に「長さ  a 以上の区間の個数」がどうなったかを数えて、それが偶数だったら先手勝ち

全探索して先手勝ちになるパターンが存在しなかったら、後手勝ち。

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

bool solve(long long a, long long b, const string &S) {
    vector<long long> v;
    int N = S.size();

    // ... を区間ごとに切り出す
    for (int i = 0; i < N; ++i) {
        if (S[i] == '.') {
            int j = i + 1;
            while (j < N && S[j] == '.') ++j;

            // b 以上 a 未満あったら負け
            if (j - i >= b && j - i < a) return false;

            if (j - i >= a) v.push_back(j - i);
            i = j;
        }
    }
    sort(v.begin(), v.end(), greater<long long>());
    
    // 初手何もできなかったら負け
    if (v.empty()) return false;

    // 2b 以上を残したら負け (まず 2b 以上が 2 箇所以上あったら負け)
    if (v.size() >= 2 && v[1] >= b*2) return false;

    // 全探索 (v[0] を分割する)
    for (long long i = 0; i + a <= v[0]; ++i) {
        long long j = v[0] - i - a;

        // 2b を与えてはいけない
        if (i >= b*2 || j >= b*2) continue;

        // b 以上 a 未満を与えてはいけない
        if (i >= b && i < a) continue;
        if (j >= b && j < a) continue;

        // 操作後に「a 以上」の区間が何個残るかを数える
        int con = 0;
        if (i >= a) ++con;
        if (j >= a) ++con;
        con += (int)v.size() - 1;
        if (con % 2 == 0) return true;
    }
    return false;
}

int main() {
    int CASE; cin >> CASE;
    while (CASE--) {
        long long a, b; string S;
        cin >> a >> b >> S;
        if (solve(a, b, S)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}