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; }