Codeforces #215 Div1. A. Sereja and Algorithm

CF215に参加。
本番ABCをsubmitするも、Bは結果TLE。CはいったんHackされてResubmit。
WAも多くグダグダだったがCが正解できたので幸いレートは維持。
Dもアプローチは正しかったのでもう一息だったな。
http://codeforces.com/contest/367/problem/A

問題

x,y,zで構成される文字列Qに対し、以下の手順を行う。

• Q中に"zyx""xzy""yxz"のいずれでもない３文字の部分文字列ものがあれば、その３文字の並びを変える、という処理を繰り返す。そのような文字が無ければ処理を終了。

x,y,zで構成されるSに対し、部分文字列の先頭・末尾を示す数列L[i],R[i]が与えられる。
各L[i],R[i]に置ける部分文字列S[L[i]...R[i]]に対し、上記処理が処理終了できるかを答えよ。

解法

処理が終了できるのは次のいずれか。

• 部分文字列が２文字以下
• xzyxzyxzy....とxyzを繰り返した形になる

前者はL[i]とR[i]がわかれば明確。
後者は、S[L[i]...R[i]]におけるx,y,zの個数の差が１以下なら良い。
これは前処理でS[0..x]のx,y,zの数を数えておけばO(1)で求まる。

string S;
int N,M;
int X[100001],Y[100001],Z[100001];

int dodo(int xx,int yy,int zz) {
	if(xx+yy+zz<3) return 1;
	if(xx==zz && xx==yy) return 1;
	
	if(xx==zz && xx==yy+1) return 1;
	if(xx==zz+1 && xx==yy+1) return 1;
	if(zz==yy && zz==xx+1) return 1;
	if(zz==yy+1 && zz==xx+1) return 1;
	if(yy==xx && yy==zz+1) return 1;
	if(yy==xx+1 && yy==zz+1) return 1;
	return 0;
}

void solve() {
	int f,i,j,k,l,x,y,r;
	
	cin>>S>>M;
	N=S.size();
	FOR(i,N) {
		X[i+1]=X[i];
		Y[i+1]=Y[i];
		Z[i+1]=Z[i];
		if(S[i]=='x') X[i+1]++;
		if(S[i]=='y') Y[i+1]++;
		if(S[i]=='z') Z[i+1]++;
	}
	
	FOR(i,M) {
		cin>>l>>r;
		if(dodo(X[r]-X[l-1],Y[r]-Y[l-1],Z[r]-Z[l-1])) _P("YES\n");
		else _P("NO\n");
	}
	
}

まとめ

もっと短く書けるな…。
本番は「２文字以下」のケースを見事に見落として1WA。
最初見落としてもpretest通って、その後rejudgeでWA食らった…。
ほんとミスが多いわ。