読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #164 Div2. D. Wall Bars

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

問題

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

解法

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

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

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

最後は、直前の脚がまだH+1以上離れたことが無いなら、他の3本の脚の高さにかかわらず答えに加算。
H+1以上離れているなら、他の3本が1本でもH+1以上離れていない数値のみ加算。
「他の3本の脚の高さ」を昇順で管理することで計算量を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)は自力では思いつかん…。
このように配列要素を回転させながら使うことで、次元を1つ落とすDPは覚えておかないとな。

広告を非表示にする