Codeforces ECR #093 : F. Controversial Rounds

またややこしい問題。
https://codeforces.com/contest/1398/problem/F

問題

01で構成された文字列を考える。
f(A,k) := 文字列A中でk個0または1が連続した文字列が、互いに重複しない部分文字列として登場する最大数
とする。
文字列Sが与えられる。Sは一部ワイルドカードになっている。
この値を任意に決められるとき、k=1～Nにおいてf(S,k)を求めよ。

解法

ワイルドカードは文字を選べるというより、今部分列を構成するときに邪魔しないもの、と考える。

k=1～Nについて、順に求めて行こう。
先頭から、貪欲に0/1をk個並べられるか判断し、現在位置からk個0または1を連続で取れるか判定していこう。
ダメな時は、次の01異なる位置にジャンプする。
その際、「現在位置からk個0または1を連続で取れない」とわかった場合、以後kが大きくなってきたときもその位置からk個0または1を連続で取れないことは確定する。

そこで、「現在位置からk個0または1を連続で取れるかもしれない」という位置を管理しておき、取れないことが確定した場合はその位置を忘れていくことで、同じ位置について繰り返し処理を行うことを避けられる。

int N;
string S;
int nex[1010101][3];
int num[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	set<int> alive;
	cin>>N>>S;
	nex[N][0]=nex[N][1]=nex[N][2]=N;
	
	for(i=N-1;i>=0;i--) {
		nex[i][0]=nex[i+1][0];
		nex[i][1]=nex[i+1][1];
		nex[i][2]=nex[i+1][2];
		if(S[i]=='0') nex[i][0]=i;
		if(S[i]=='1') nex[i][1]=i;
		if(S[i]=='?') nex[i][2]=i;
	}
	for(i=0;i<=N;i++) alive.insert(i);
	for(i=1;i<=N;i++) {
		int cur=0;
		while(cur<N) {
			cur=*alive.lower_bound(cur);
			
			
			x=max(nex[cur][0],nex[cur][1]);
			//cout<<"!"<<cur<<" "<<num[i]<<" "<<x<<endl;
			if(x-cur>=i) {
				num[i]+=(x-cur)/i;
				cur+=(x-cur)/i*i;
			}
			else {
				
				if(S[cur]=='?') {
					alive.erase(cur);
					cur++;
				}
				else {
					auto it=alive.lower_bound(cur);
					while(1) {
						if(it!=alive.end() && *it<x && *it<nex[cur][2]) {
							it=alive.erase(it);
						}
						else break;
					}
				}
			}
		}
		cout<<num[i]<<" ";
	}
	cout<<endl;
}

まとめ

ECRのFにしては簡単？