think-cell Round 1 : D2. Sum over all Substrings (Hard Version)

コードは短い。
https://codeforces.com/contest/1930/problem/D2

問題

M文字のバイナリ文字列pに対し、バイナリ文字列qがp-goodであるとは、p[i]に対し、p[i]がq[l...r]の中央値となるl≦i≦rが存在することを意味する。
また、f(p)はそのようなqのうち1の個数の最小値とする。

文字列sが与えられるので、sの部分列s'に対し、f(s')の総和を求めよ。

解法

p[i]=1の場合、q[i-1]かq[i]かq[i+1]に1があればよいことになる。
よって、qは"0"か"010"をつなげた文字列であればよい。
dp(n) := [i..n]文字目の部分文字列のうち1の個数
とするとp[i]=1の時、dp(n)=n+1+dp(n-3)となる。

int T,N;
string S;

ll dp[1010101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>S;
		
		FOR(i,N+10) dp[i]=0;
		
		ll ret=0;
		if(S[0]=='1') {
			dp[0]=1;
			ret++;
		}
		for(i=1;i<N;i++) {
			if(S[i]=='0') {
				dp[i]=dp[i-1];
			}
			else {
				dp[i]=i+1+(i-3>=0?dp[i-3]:0);
			}
			ret+=dp[i];
		}
		cout<<ret<<endl;
	}
}

まとめ

本番これどう解いたんだろ。Easy解いて実験したのかな。