mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #215 (Div. 1) A. Sereja and Algorithm

解法

まず, 2 文字以下なら絶対にアルゴリズムは終了します。

3 文字以上の時は, xzy または yxz または zyx が繰り返し並ぶ構造になっていれば収束しますが, これは 指定された区間における x, y, z の数が区間の長さの大体 1/3 になっていれば良いということなので, そうなっているかチェックします。

const int MAXN = 100010;
int X[MAXN], Y[MAXN], Z[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    for (int i = 1; i <= n; i++) {
        X[i] = X[i-1]+(s[i-1]=='x');
        Y[i] = Y[i-1]+(s[i-1]=='y');
        Z[i] = Z[i-1]+(s[i-1]=='z');
    }
    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        int num = r-l+1;
        if (num < 3) {
            cout << "YES" << endl;
            continue;
        }
        int x = X[r]-X[l-1], y = Y[r]-Y[l-1], z = Z[r]-Z[l-1];
        if (num%3 == 0) {
            if (x==num/3 && y==num/3 && z == num/3) {
                cout << "YES" << endl;
            } else cout << "NO" << endl;
        } else if (num%3==1) {
            bool ok = false;
            if (x==num/3+1) if (y==num/3 && z==num/3) ok = true;
            if (y==num/3+1) if (x==num/3 && z==num/3) ok = true;
            if (z==num/3+1) if (y==num/3 && x==num/3) ok = true;
            if (ok) cout << "YES" << endl;
            else cout << "NO" << endl;
        } else if (num%3 == 2) {
            bool ok = false;
            if (x==num/3) if (y==num/3+1 && z==num/3+1) ok = true;
            if (y==num/3) if (x==num/3+1 && z==num/3+1) ok = true;
            if (z==num/3) if (y==num/3+1 && x==num/3+1) ok = true;
            if (ok) cout << "YES" << endl;
            else cout << "NO" << endl;
        }
    }
    return 0;
}