TopCoder SRM 782 : Div1 Easy Div2 Hard EmptyTheBox

変わった上限の問題。
https://community.topcoder.com/stat?c=problem_statement&pm=16039&rd=17900

問題

整数D,Tが与えられる。
それぞれ1～Tの整数が書かれた箱が1つずつある。
ここで以下の作業を繰り返す。

• D面ダイスを2つ振り、出た目の和をSとする。
• 箱のうち、書かれた整数の和がSとなる範囲で任意個数取り除く。そのような取り除き方ができない場合終了。できたらまた上に戻る。

残された箱の整数の和をペナルティとする。
ペナルティを最小にするような箱の取り除き方をしたとき、その期待値を求めよ。

解法

箱のうち2Dより大きな値のものは絶対に取り除けない。
よって以降2D以下の値のもののみ考える。
といっても2D≦12なので、2^(2D)通り残った箱の状態を持ってO(D*3^(2*D))かかるbitdpで間に合う。

double dp[1<<12]={};
int sum[1<<12];
double P[13];

class EmptyTheBox {
	public:
	double minExpectedPenalty(int D, int T) {
		ll ret=0;
		while(T>2*D) ret+=T, T--;
		
		int i,j;
		FOR(i,1<<12) {
			sum[i]=0;
			FOR(j,12) if(i&(1<<j)) sum[i]+=j+1;
		}
		
		int x,y;
		FOR(i,13) P[i]=0;
		for(x=1;x<=D;x++) {
			for(y=1;y<=D;y++) {
				P[x+y]+=1.0/(D*D);
			}
		}
		
		int mask;
		dp[0]=ret;
		for(mask=1;mask<(1<<T);mask++) {
			double Q[13];
			FOR(i,2*D+1) Q[i]=ret+sum[mask];
			for(int sm=mask-1; sm>=0; sm--) {
				sm&=mask;
				if(2<=sum[mask]-sum[sm] && sum[mask]-sum[sm]<=2*D) Q[sum[mask]-sum[sm]]=min(Q[sum[mask]-sum[sm]],dp[sm]);
			}
			dp[mask]=0;
			for(i=2;i<=2*D;i++) dp[mask] += P[i]*Q[i];
		}
		
		return dp[(1<<T)-1];
		
		
	}
}

まとめ

Easyの割とに実装量多め？
300ptとは言わないまでも275ptとかでもいいかもね。