AtCoder ARC #065 : F - シャッフル / Shuffling

頭がこんがらがる。
http://arc065.contest.atcoder.jp/tasks/arc065_d

問題

01で構成されたN文字の文字列Sがある。
ここに以下のM個のクエリが与えられる。
各クエリiは区間[L[i],R[i]]で構成され、S[L[i]...R[i]]を任意にシャッフルできることを意味する。
L[i]は非減少である。

最終的に得られる文字列の組み合わせを求めよ。

解法

尺取り法の要領で解く。
dp(x,y) := Sのx文字目までに0がy回出てくるような組み合わせの数

x+1文字目を0にするか1にするかを考える。
x+1∈(L[i],R[i])となるようなクエリにおけるR[i]の最大値をMR(x+1)とする。
x+1文字目には、SのうちMR(x+1)文字目までのいずれかの文字を持ってこれる。

MR(x+1)文字目までの0,1の登場回数と、x文字目までの0,1の登場回数がわかっていれば、x+1文字目に0,1をそれぞれ配置可能かわかる。
あとはDPでdp(x,y)を更新していき、dp(N,S中の0の数)を答えればよい。

int N,M;
string S;
ll mo=1000000007;
ll dp[3030][3030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S;
	
	int CR=0,CL=0;
	int B[2]={};
	dp[0][0]=1;
	while(M--) {
		int L,R;
		cin>>L>>R;
		L--,R--;
		while(CL<L) {
			if(CL==CR) B[S[CR++]=='1']++;
			FOR(i,3001) if(dp[CL][i]) {
				if(i<B[0]) (dp[CL+1][i+1]+=dp[CL][i])%=mo;
				if(CL-i<B[1]) (dp[CL+1][i]+=dp[CL][i])%=mo;
			}
			CL++;
		}
		while(CR<=R) B[S[CR++]=='1']++;
	}
	while(CL<N) {
		if(CL==CR) B[S[CR++]=='1']++;
		FOR(i,3001) if(dp[CL][i]) {
			if(i<B[0]) (dp[CL+1][i+1]+=dp[CL][i])%=mo;
			if(CL-i<B[1]) (dp[CL+1][i]+=dp[CL][i])%=mo;
		}
		CL++;
	}
	
	cout<<dp[CL][B[0]]<<endl;
}

まとめ

こちらの方がコードは単純。