Codeforces #164 Div2. D. Wall Bars

さて本番解けなかった問題D。
周りを見ても、EよりDの方が正解者が少ないようだ。
http://www.codeforces.com/contest/268/problem/D

問題

中央の棒を取り囲むように４本の脚がある遊具がある。
1～Nの高さで、それぞれ１本ずつ中央といずれかの脚に棒を渡す。
遊具は４本の脚のいずれかが棒同士がH+1以上離れていないような構成を取れる、棒の配置の数を答える。

解法

最初４本の脚それぞれでH+1以上離れたかどうかおよび一番近い棒の高さを覚えてDPしようとした。
でも、４本の脚で棒の高さを覚えると１回O(H^4)の計算が必要なので、全部でO(NH^4)とTLEしてしまう。

そこでEditorialの手法で対応。
直前の棒を渡した脚がすでにH+1以上離れたかまだ離れていないか、そして現在位置から残り３本の脚までの高さを状態に持つ。
この高さが0ならその脚はすでにH+1以上離れたことがあり、1以上ならまだ離れていない、とみる。

高さを1～Nまで処理してDPする。
直前と同じ脚に棒を渡すなら、その時の組み合わせ数を残り３本の脚の高さを1減らしたカウンタに加算する。
他の脚に棒を渡すなら、直前の脚と残り２本の脚の高さで３本の脚の高さの状態を表すよう配列要素を入れ替えてカウンタに加算する。

最後は、直前の脚がまだH+1以上離れたことが無いなら、他の３本の脚の高さにかかわらず答えに加算。
H+1以上離れているなら、他の３本が１本でもH+1以上離れていない数値のみ加算。
「他の３本の脚の高さ」を昇順で管理することで計算量を1/6に減らしている。

int N,H;
ll DP[2][2][32][32][32];
ll MO=1000000009;


void solve() {
	int x,y,i,j,res,TM,nc,th[4];
	ll o,p;
	
	GET2(&N,&H);
	DP[0][1][H][H][H]=1;

	for(y=1;y<=N;y++) {
		int cur=(y-1)%2;
		int tar=y%2;
		ZERO(DP[tar]);
		
		FOR(th[0],H+1) for(th[1]=th[0];th[1]<=H;th[1]++) for(th[2]=th[1];th[2]<=H;th[2]++) {
			FOR(x,2) {
				ll& cv=DP[cur][x][th[0]][th[1]][th[2]];
				if(cv==0) continue;
				//same
				ll& dps=DP[tar][x][max(th[0]-1,0)][max(th[1]-1,0)][max(th[2]-1,0)];
				dps=(dps + cv)%MO;
				
				if(x==0) {
					ll& dp1=DP[tar][th[0]>0][0][max(th[1]-1,0)][max(th[2]-1,0)];
					dp1=(dp1 + cv)%MO;
					
					ll& dp2=DP[tar][th[1]>0][0][max(th[0]-1,0)][max(th[2]-1,0)];
					dp2=(dp2 + cv)%MO;
					
					ll& dp3=DP[tar][th[2]>0][0][max(th[0]-1,0)][max(th[1]-1,0)];
					dp3=(dp3 + cv)%MO;
				}
				else {
					ll& dp1=DP[tar][th[0]>0][max(th[1]-1,0)][max(th[2]-1,0)][H-1];
					dp1=(dp1 + cv)%MO;
					
					ll& dp2=DP[tar][th[1]>0][max(th[0]-1,0)][max(th[2]-1,0)][H-1];
					dp2=(dp2 + cv)%MO;
					
					ll& dp3=DP[tar][th[2]>0][max(th[0]-1,0)][max(th[1]-1,0)][H-1];
					dp3=(dp3 + cv)%MO;
				}
			}
			
		}
	}
	
	o=0;
	i=N%2;
	FOR(x,2) {
		FOR(th[0],H+1) for(th[1]=th[0];th[1]<=H;th[1]++) for(th[2]=th[1];th[2]<=H;th[2]++) {
			if(x || th[2]) {
				o+=DP[i][x][th[0]][th[1]][th[2]];
				o %= MO;
			}
		}
	}
	_P("%lld\n",o);
	
	return;
}

まとめ

うーん、O(NH^4)の解法は思いついたけどO(NH^3)は自力では思いつかん…。
このように配列要素を回転させながら使うことで、次元を１つ落とすDPは覚えておかないとな。