TopCoder SRM 615 Div1 Hard AlternativePiles

問題

一列にカードが並んでいて、i番目のカードの色はC[i]で与えられ、R, G, B, Wのどれか。
整数Mが与えられるとき、Wのカードに以下の条件を満たすようにR, G, Bの色を塗る塗り方は何通りあるか、mod 10^9+7で求めよ。

条件：
適当な整数Dをきめたとき、R, GがちょうどM*Dこずつある。
長さ2*Dの数列M組であって、
i番目の数列をS_iとすると、
C[S_i[j]] = 'R' (jが偶数のとき）
C[S_i[j]] = 'G' (jが奇数のとき）
を満たしており、どの異なる二つのS_iも同じ要素を持たないような数列の組S_iをとることができる。

制約条件

カードの枚数≦5000
M≦50

方針

カードからBであるものを取り除いた並びが、
RRRGGGRRRGGGのような並びをしていてほしい。

これはD = 2, M = 4のときに条件を満たしている。
このような並びがS_iを取れるというのはどういう条件を満たしているか考える。

まずはR, GがMの倍数個出現していないとならない。

任意のiについて、先頭i文字を見たとき、
Rの出現した個数＜Gの出現した個数になっているとダメ
Rの出現した個数＞Gの出現した個数 + Mになっているとダメ。

逆に|G|≦|R|≦|G| + Mを満たすとき、必ずSが取れることがわかる。
（後ろからG, R, G, Rととっていけば条件を崩さないように取れるから）

なので、dp[pos][Rの個数 - Gの個数][Rの個数 % M] := 場合の数
というDPをすればよい。

ソースコード

const int mod = (int)1e9 + 7;

int dp[2][60][60];

class AlternativePiles {
	public:
	int count(string C, int M) {
		int n = C.size();
		
		memset(dp, 0, sizeof(dp));
		
		dp[0][0][0] = 1;
		int cur = 0, next = 1;
		
		rep(i, n){
			memset(dp[next], 0, sizeof(dp[next]));
			
			rep(j, M + 1) rep(l, M + 1) if(dp[cur][j][l]) rep(k, 3){
				
				if(C[i] != 'W' && C[i] != "RBG"[k]) continue;
				
				int nj = j + 1 - k;
				int nl = (l + (k == 0)) % M;
				
				if(0 <= nj && nj <= M){
					dp[next][nj][nl] += dp[cur][j][l];
					if(dp[next][nj][nl] >= mod) dp[next][nj][nl] -= mod;
				}
			}
			swap(cur, next);
		}
		return dp[cur][0][0];
	}
};