TopCoder SRM 777 : Div2 Hard BlackAndWhiteBallsEasy

Div1 Hardはどうにもなんなかったけど。
https://community.topcoder.com/stat?c=problem_statement&pm=15921&rd=17802

問題

Nマスが連続しており、それぞれ白か黒に塗られている。
2つの正整数W,Bが与えられる。
まず、マス目をいくつかに区切り、区切った範囲が白マスがW個含まれるか、黒マスがB個含まれるようにする。
区切った範囲を、それぞれ条件を満たした場合に'W','B'に置き換えるとする。(両方条件を満たすならどちらに置き換えてもよい)。
そうして得られる文字列は何通りか。区切り方が異なっても、文字の置き換えた結果が等しければ等しいとみなす。

解法

f(i) := Nマスのprefix iマスを区切って置き換えたとき、ユニークな置き換え方の数
とする。次の区切り目を区間[i+1,j]マス目とするとき、f(j) += f(i) * g(i+1,j) (g(L,R)は、区間[L,R]が上記2条件のうち何条件を満たすか)で値を更新していけばよい。

ll dp[2525];
const ll mo=1000000007;

class BlackAndWhiteBallsEasy {
	public:
	int getNumber(vector <int> balls, int white, int black) {
		string S;
		int i;
		FOR(i,balls.size()) S+=string(balls[i],i%2);
		int N=S.size();
		ZERO(dp);
		
		dp[0]=1;
		FOR(i,N) {
			int j;
			int C[2]={};
			for(j=i;j<N;j++) {
				C[S[j]]++;
				if(C[0]==white) (dp[j+1]+=dp[i])%=mo;
				if(C[1]==black) (dp[j+1]+=dp[i])%=mo;
			}
		}
		return dp[N];
	}
}

まとめ

よくまぁこういう問題思いつくよね。