Codeforces #505 C. Plasticine zebra

Hackで稼いでHighest近くまで回復した。
http://codeforces.com/contest/1025/problem/C

問題

bとwで構成される文字列がある。
この文字列に対し、以下の処理を任意回数行えるとする。

• 文字列の中で１か所区切り目を入れる。区切り目の前と後をそれぞれ反転し、再度連結する

こうして構築できる文字列において、bとwが最長何個連続するか。

解法

この処理を行うと何が起きるか、具体的な文字列で行うとはっきりする。
例えば12345|678のように区切ると54321|876となる。
これは、元の文字列を反転させたうえローテートした状態となる。

文字列を反転してもbwの連続数は変わらない。
よって、この問題は文字列のローテートを許可した場合、bwが交互に登場する最長列を求める問題になる。

あとはこのような問題の定番テクとして、文字列を２倍化し、最長列を求めよう。

int N;
string S;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	S=S+S;
	int ret=0;
	int pre=-1;
	int cur=0;
	FORR(c,S) {
		if(pre==-1 || c==pre) cur=0;
		cur++;
		pre=c;
		ret=max(ret,cur);
	}
	cout<<min(N,ret)<<endl;
	
}

まとめ

考察部分が主の問題。