Codeforces #592 Div2 F. Stack Exterminable Arrays

Div2で7問もあるけど簡単だったっぽい。
https://codeforces.com/contest/1244/problem/F

問題

白黒の石がN個リング状に連なっている状態を考える。
1回処理を行うと、石の色は以下のように変化する。

• その石と両隣の石の計3つの石の色のうち、最大手のものになる。

K回処理を行った後の状態を求めよ。

解法

初期状態で白黒交互に並んでいる場合、処理毎に白黒反転する。

そうでない場合、2つ同じ色の石が並んでいると、それ以上そこは変化しないし、むしろその両隣の石を同じ色に染めていく。
そこで、各石について最寄りの「同じ色の石の並び」からの距離を求めよう。
それがK以下ならその最寄りの石の色になるし、それまでは白黒交互に代わる。

int N,K;
string S;
int F[202020],NF;
int D[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>S;
	FOR(i,N) {
		if(S[i]==S[(i+1)%N] || S[i]==S[(i+N-1)%N]) F[i]=1, NF++;
	}
	
	if(NF==0) {
		if(K%2) {
			FORR(c,S) c='B'+'W'-c;
		}
		cout<<S<<endl;
		return;
	}
	
	FOR(i,N) D[i]=1<<20;
	FOR(i,N) if(F[i]) {
		int cur=0;
		FOR(j,N) {
			if(F[(i+j)%N]==1) cur=0;
			else {
				cur++;
				D[(i+j)%N]=cur;
			}
		}
		cur=0;
		FOR(j,N) {
			if(F[(i+N-j)%N]==1) cur=0;
			else {
				cur++;
				D[(i+N-j)%N]=min(D[(i+N-j)%N],cur);
			}
		}
		
		break;
	}
	
	FOR(i,N) if(F[i]==0) {
		if(D[i]<=K) {
			if(D[i]%2==1) S[i]='B'+'W'-S[i];
		}
		else {
			if(K%2==1) S[i]='B'+'W'-S[i];
		}
	}
	cout<<S<<endl;
}

まとめ

Div2 Dぐらいの難易度に感じる。