Codeforces Round #625 (Div. 1) D. Reachable Strings (R2500)

まさか残り 25 分で通し切れるとは思わなかった！

問題へのリンク

問題概要

長さ の '0' と '1' のみからなる文字列 が与えられる。以下の 個のクエリに答えよ

• 各クエリは left, right, len からなる
• 部分文字列 A = S[left : left + len], B = S[right: right + len] を考える
• A に所定の操作を好きな順序で好きな回数だけ施して B に一致させられるかどうかを判定せよ

操作は

• 文字列の連続する 3 文字であって "011" であるものを "110" に置き換える
• 文字列の連続する 3 文字であって "110" であるものを "011" に置き換える

のいずれかである

制約

• 

考えたこと

こういうのはまず初めに「2 つの文字列 A, B が与えられて、互いに変換できるか」を考えることにする。それができてわかりやすい特徴づけができたら、改めて、クエリを高速に答える方法を考えることにしよう。

まず注目したいことは

• S を T に変換できるなら、T から S にも変換できる
• 0 と 1 の個数は変化しない

といったあたり。よって、「1 の個数」が異なっていたら、その時点で No である。さらに 1 個目の特徴から、こういう考え方ができる

• 操作を繰り返すことで、なにかある種の「標準形」を見出してあげて、それが一致するかどうかで判定する

ということ。こういう考え方をする問題は非常に数多くある。今回の操作は「0 を 2 個前にずらしたり 2 個後ろにずらしたりする」という操作だと読み替えられるので、0 をできるだけ前に動かすことにしよう。

そうすると、たとえば 110111011010 とかは、こんな風になる。

010010111111

つまり、

• 1 個目の 0 の左には 1 が偶数個あるので、一番左に持ってこれる
• 2 個目の 0 と 1 個目の 0 との間には 1 が奇数個あるので、1 を 1 個だけ残して左に持ってくる
• 3 個目の 0 と 2 個目の 0 との間には 1 が偶数個なので、2 個目の 0 のところまで 0 を持ってこれる
• 4 個目の 0 と 3 個目の 0 との間には 1 が奇数個あるので、1 を 1 個だけ残して 0 を持ってくる
• 残りは全部 1

という感じだ。つまり標準形は、 i 個目の 0 の手前にある 1 の個数を s[ i ] として、s[ i ] - s[ i -1 ] のパリティで決まるのだ。以上から、A を B に変換できる条件は、以下のように記述できる。

---

• A と B とで 1 の個数が等しい
• A と B とで、それぞれの 0 について、その手前にある 0 までの間の 1 の個数のパリティを並べたベクトルとが一致する

---

クエリ

元の問題に戻って、A = S[left : left + len], B = S[right: right + len] とで、A や B の前にある 1 の個数のパリティがもし等しかったら、A と B それぞれの 0 についての上記のパリティベクトルが一致するかどうかは、ロリハなどを使って判定できる。

A と B の前にある 1 の個数のパリティが異なっていたら、パリティ反転したロリハを用意すれば同じように判定できる。

計算量は

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

struct RollingHash {
    static const int base1 = 1007, base2 = 2009;
    static const int mod1 = 1000000007, mod2 = 1000000009;
    vector<long long> hash1, hash2, power1, power2;

    // construct
    RollingHash(const vector<int> &S) {
        int n = (int)S.size();
        hash1.assign(n+1, 0);
        hash2.assign(n+1, 0);
        power1.assign(n+1, 1);
        power2.assign(n+1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i+1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i+1] = (hash2[i] * base2 + S[i]) % mod2;
            power1[i+1] = (power1[i] * base1) % mod1;
            power2[i+1] = (power2[i] * base2) % mod2;
        }
    }
    
    // get hash of S[left:right]
    inline pair<long long, long long> get(int l, int r) const {
        long long res1 = hash1[r] - hash1[l] * power1[r-l] % mod1;
        if (res1 < 0) res1 += mod1;
        long long res2 = hash2[r] - hash2[l] * power2[r-l] % mod2;
        if (res2 < 0) res2 += mod2;
        return {res1, res2};
    }

    // get lcp of S[a:] and S[b:]
    inline int getLCP(int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }

    // get lcp of S[a:] and T[b:]
    inline int getLCP(const RollingHash &T, int a, int b) const {
        int len = min((int)hash1.size()-a, (int)hash1.size()-b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a+mid) != T.get(b, b+mid)) high = mid;
            else low = mid;
        }
        return low;
    }
};

int N;
string S;
vector<int> ones;
vector<int> ids, pars, ipars;

bool solve(int left, int right, int len, RollingHash &rh, RollingHash &irh) {
    if (ones[right+len] - ones[right] != ones[left+len] - ones[left]) return false;
    int lpar = ones[left] % 2;
    int rpar = ones[right] % 2;
    int lid = lower_bound(ids.begin(), ids.end(), left) - ids.begin();
    int lid2 = lower_bound(ids.begin(), ids.end(), left + len) - ids.begin();
    int idlen = lid2 - lid;
    int rid = lower_bound(ids.begin(), ids.end(), right) - ids.begin();
    if (lpar == rpar) return rh.get(lid, lid + idlen) == rh.get(rid, rid + idlen);
    else return irh.get(lid, lid + idlen) == rh.get(rid, rid + idlen);
}

int main() {
    while (cin >> N >> S) {
        ones.assign(N+1, 0);
        for (int i = 0; i < N; ++i) {
            int add = 0;
            if (S[i] == '1') add = 1;
            ones[i+1] = ones[i] + add;
        }

        ids.clear(); pars.clear(), ipars.clear();
        int num = 0;
        for (int i = 0; i < N; ++i) {
            if (S[i] == '0') pars.push_back(num % 2), ids.push_back(i);
            else ++num;
        }
        for (int i = 0; i < pars.size(); ++i) ipars.push_back(1 - pars[i]);

        RollingHash rh(pars), irh(ipars);

        int Q; cin >> Q;
        while (Q--) {
            int left, right, len;
            cin >> left >> right >> len;
            --left;
            --right;
            if (solve(left, right, len, rh, irh)) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
    }
}