Codeforces #1014 : Div2 F. Andryusha and CCB

気が付いてしまえば簡単かも。
https://codeforces.com/contest/2092/problem/F

問題

バイナリ文字列Zの美しさとは、隣接文字のうち異なっている箇所の数とする。
ある文字列TをK個の連続部分列に分割したとき、それぞれの美しさが一致するようにしたい。

バイナリ文字列Sが与えられる。
Sのprefixごとに、美しさが一致する分割法としてあり得るKの個数を答えよ。

解法

(美しさ,K)の対を考えると、それを満たすSのprefixは区間を成す。
あらかじめSをRLE圧縮しておけば、上記に対する区間を容易に求められる。

int T,N;
string S;

int ret[1<<20];
int seg[1<<20];

vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		V.clear();
		FOR(i,N) {
			if(V.empty()||S[i]!=S[V.back().first]) V.push_back({i,0});
			V.back().second++;
			seg[i]=i+2-V.size();
			ret[i]=0;
		}
		for(int m=2;m<=V.size();m++) {
			for(k=1;;k++) {
				if(k==1) {
					x=y=m-1;
				}
				else {
					
					if(V[x].second>=2) {
						x+=m-1;
					}
					else {
						x+=m;
					}
					y+=m;
				}
				if(x>=V.size()) break;
				y=min(y,(int)V.size()-1);
				ret[V[x].first]++;
				ret[V[y].first+V[y].second]--;
			}
		}
		int pat=0;
		FOR(i,N) {
			ret[i+1]+=ret[i];
			seg[i]+=ret[i];
			_P("%d ",seg[i]);
		}
		_P("\n");
	}
}

まとめ

CCBってなんだろ？