TopCoder SRM 554 Div2 Hard TheBrickTowerHardDivTwo

続いてSRM554。Div2 HardはDiv1 Hardの制限を大幅に緩めた問題となっている。
http://community.topcoder.com/stat?c=problem_statement&pm=12164

問題

1x1x1の大きさの立方体を、幅2x奥行2を１段分として1段ずつ積んで直方体を作っていく。
この時、各立方体はC色のいずれかを持ち、また最大K組まで隣接する立方体が同じ色を持っていても良い。

1～H段の各直方体において、上記条件を満たす立方体の積み方の組み合わせを答えよ。

解法

C<=4なので、１段分４マスの色の組み合わせは4^4=256通り。
よって、DP[最上段の色の組み合わせ][同色の立方体の組数]と状態を取って１段ずつDPで組み合わせ数を求めていけばよい。

１段ごとに、現在最上段の色の組み合わせが256通り、その上の段に積む組みわせが256通り、同色の立方体の組数がK<=7通りなので、H<=47段分繰り返しても問題ない。

単純なDP問題だね。

ll mo=1234567891;
ll dpdp[2][256][8];

class TheBrickTowerHardDivTwo {
	public:
	int find(int C, int K, int H) {
		ll tot=0;
		int mask,mask2,c[4],d[4],x,y,h;
		
		ZERO(dpdp);
		
		FOR(mask,256) {
			int n=0;
			c[0]=mask%4; c[1]=mask/4%4;	c[2]=mask/16%4;	c[3]=mask/64%4;
			if(c[0]>=C || c[1]>=C ||c[2]>=C ||c[3]>=C) continue;
			n=(c[0]==c[1])+(c[0]==c[2])+(c[1]==c[3])+(c[2]==c[3]);
			if(n<=K) {
				dpdp[0][mask][n]=1;
				tot++;
			}
		}
		
		for(h=1;h<H;h++) {
			int cur=(h-1)&1;
			int tar=h&1;
			ZERO(dpdp[tar]);
			
			FOR(mask,256) {
				c[0]=mask%4; c[1]=mask/4%4;	c[2]=mask/16%4;	c[3]=mask/64%4;
				if(c[0]>=C || c[1]>=C ||c[2]>=C ||c[3]>=C) continue;
				FOR(mask2,256) {
					d[0]=mask2%4; d[1]=mask2/4%4; d[2]=mask2/16%4;	d[3]=mask2/64%4;
					if(d[0]>=C || d[1]>=C || d[2]>=C ||d[3]>=C) continue;
					
					int n=(d[0]==d[1])+(d[0]==d[2])+(d[1]==d[3])+(d[2]==d[3]);
					n+=(d[0]==c[0])+(d[1]==c[1])+(d[2]==c[2])+(d[3]==c[3]);
					FOR(x,K+1) if(n+x<=K) dpdp[tar][mask2][n+x] +=dpdp[cur][mask][x];
				}
			}
			
			FOR(mask2,256) FOR(x,K+1) tot += dpdp[tar][mask2][x] %= mo;
			tot %= mo;
		}
		return (int)tot;
	}
};

まとめ

さっきのSRM555といいそこまで手の込んでないDP問題だ。