Recruit Programming Contest 模擬練習会 : B - ブロック並べ

うーん、あまり面白くないかも…。
http://recruit-programing-contest-practice.contest.atcoder.jp/tasks/recruite_2013_pre_b

問題

R個の赤色のブロックとB個の青色のブロックを１列に並べる。
連続するRn個のブロック中にRk個以上赤ブロックがなく、連続するBn個のブロック中にBk個以上青ブロックがないようなブロックの並べ方の組み合わせ数を答えよ。

解法

Rn,Bnは高々9なので、直前の9つのブロックの内容を覚えながらDPすればよい。
O(R*B*2^(max(Rn,Bn)))程度の時間で終わる。
RやBは20以下なので余裕。

ll mo=1000000009;
ll dpdp[21][21][1025];

void solve() {
	int f,i,j,k,l,x,y,xx,rr,bb;
	int N,T;
	
	cin>>T;
	FOR(xx,T) {
		int R,B,Rn,Rk,Bn,Bk;
		cin>>R>>B>>Rn>>Rk>>Bn>>Bk;
		
		ZERO(dpdp);
		dpdp[0][0][0]=1;
		
		FOR(i,R+B) {
			FOR(rr,R+1) {
				bb=i-rr;
				if(bb<0 || bb>B) continue;
				
				int mask;
				FOR(mask,1<<9) {
					if(dpdp[rr][bb][mask]==0) continue;
					int rm=(1<<(min(Rn,i+1)))-1;
					int bm=(1<<(min(Bn,i+1)))-1;
					int nrm=((mask<<1)&511) | 1;
					int nbm=((mask<<1)&511) | 0;
					
					if(rr<R && __builtin_popcount(nrm&rm)<Rk) {
						dpdp[rr+1][bb][nrm] += dpdp[rr][bb][mask];
						dpdp[rr+1][bb][nrm] %= mo;
					}
					if(bb<B && __builtin_popcount((~nbm)&bm)<Bk) {
						dpdp[rr][bb+1][nbm] += dpdp[rr][bb][mask];
						dpdp[rr][bb+1][nbm] %= mo;
					}
				}
				
			}
		}
		
		ll re=0;
		FOR(i,512) re+=dpdp[R][B][i];
		cout << re%mo << endl;
	}
}

まとめ

DPのいい練習ではあるけど、面白みは少ないな。