Good Bye 2019 : F. Awesome Substrings

いまいちだった回。
http://codeforces.com/contest/1270/problem/F

問題

01で構成されるN文字の文字列が与えられる。
この部分列のうち、1が1つ以上あり、文字列長が1の登場回数の整数倍であるものは何通りか。

解法

平方分割で解く。
1だけで構成される文字列はまず最初に数え上げてしまおう。

文字列長が1の数のk倍以下のものについては、kを2～Dの範囲で操作し、(0の登場回数-(1の登場回数)*(k-1))が0になるような部分列を数え上げよう。

D倍より大きなものについては、左端を走査しつつ数えていく。
その際高々1はN/D個までしか入りえないので、そこまでの範囲で右端を伸ばしていこう。

int N;
string S;
int nex[202020];
unordered_map<ll,int> NN;
const int DI=150;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>S;
	N=S.size();
	FORR(c,S) c-='0';
	nex[N]=N+1;
	for(i=N-1;i>=0;i--) {
		nex[i]=nex[i+1];
		if(S[i]) nex[i]=i+1;
	}
	ll ret=0;
	int num=0;
	FOR(i,N) {
		if(S[i]==0) num=0;
		else num++;
		ret+=num;
	}
	for(l=2;l<=DI;l++) {
		ll cur=0;
		NN.clear();
		NN[0]++;
		FOR(i,N) {
			if(S[i]) cur+=l-1;
			else cur--;
			ret+=NN[cur];
			NN[cur]++;
		}
	}
	FOR(i,N) {
		int cur=i;
		for(j=1;j<=202000/DI+3;j++) {
			int ne=max(nex[cur],i+j*(DI+1));
			if(ne>N) break;
			int nene=min(N,nex[nex[cur]]-1);
			if(nene>=ne) {
				ne--;
				ret+=(nene-i)/j-(ne-i)/j;
			}
			cur=nex[cur];
			
		}
	}
	
	cout<<ret<<endl;
}

まとめ

本番なぜこれを思い浮かばなかったか…。