Codeforces #265 Div1 A. No to Palindromes!

CF265に参加。Aは落としたがB,Cを解いてレート維持。
http://codeforces.com/contest/464/problem/A

問題

文字列がtolerantであるとは、連続した2文字以上の部分文字列で回文なものがないものをいう。
N文字のtolerantな文字列と整数pが与えられる。

与えられた文字列に対し、辞書順で次に来るtolerantな文字列を答えよ。
ただし使える文字種はアルファベットの頭からp種類である。

解法

辞書順で答える問題なので、文字列の後ろから順に辞書順で後に来る文字を選び、そのあとに適当に文字列をくっつけて条件を満たすか判定すればよい。

例えば今の文字列がXXXXdYYYYYとし、YYYYY部分をどういじっても条件を満たせないとする。
この場合dの次の文字を使いXXXXeZZZZZの形の文字列で条件を満たすものを探す。

ZZZZZの部分を回文にならないようにするには、abcabcabc...かcbacbacba...をくっつければよい。
後はこれらが条件を満たすか判定していくだけ。

int N,P;
string S,abc,cba;

bool tole(string t) {
	int x,y,i,l=t.size();
	FOR(x,l-1) if(t[x]==t[x+1]) return false;
	FOR(x,l-2) if(t[x]==t[x+2]) return false;
	return true;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	cin>>S;
	FOR(i,N+3) {
		abc+='a'+(i%3);
		cba+='a'+(2-(i%3));
	}
	
	for(i=N-1;i>=0;i--) {
		for(x='a';x<='z';x++) if(S[i]<x && x-'a'<P) {
			string t[6];
			FOR(j,3) {
				t[j*2]=S.substr(0,i)+(char)x+abc.substr(j,N-(i+1));
				t[j*2+1]=S.substr(0,i)+(char)x+cba.substr(j,N-(i+1));
			}
			sort(t,t+6);
			FOR(j,6) if(tole(t[j])) return _P("%s\n",t[j].c_str());
		}
	}
	return _P("NO\n");
}

まとめ

回文は最短で２・３文字なのでO(N^2)の判定はする必要がない。
自分は無駄にO(N^2)どころかO(N^3)判定してTLEしてしまった。