TopCoder SRM 702 Div2 Hard SubsetSumExtreme

うーん…。
https://community.topcoder.com/stat?c=problem_statement&pm=14440

問題

N要素の数列B[i]がある。
ここでM面ダイスを使ったゲームを行う。
各面はD[i]の値が書かれており、それぞれ等確率で目が出る。

ダイスを振り、目xが出たとする。

• 数列中に和がxとなる部分列が存在するなら、それを取り除き、ゲームを継続する。
  • 選択肢が複数あるならどの取り除き方でもよい。
• 存在しないなら残りの数列の総和がゲームのスコアとなる。

スコアが最小になるような部分列の取り除き方をとる場合、スコアの期待値を求めよ。

解法

Nが小さいので、残された数列の項目をbitmaskで表し、期待値をBitDPするだけ。
取り除きかたは上記bitmaskの部分maskとなるので、O(3^N)でそのような部分maskを列挙するテクを使おう。
そうするとO(3^N * M)で解ける。

double dp[1<<12];
int sum[1<<12];

class SubsetSumExtreme {
	public:
	double getExpectation(vector <int> block, vector <int> face) {
		int B=block.size();
		int F=face.size();
		int i;
		
		ZERO(dp);
		ZERO(sum);
		
		for(int mask=1;mask<1<<B;mask++) {
			FOR(i,B) if(mask&(1<<i)) sum[mask] += block[i];
			FOR(i,F) {
				double mi=sum[mask];
				for(int mask2=mask;;mask2=(mask2-1)&mask) {
					if(sum[mask2]==face[i]) mi=min(mi,dp[mask^mask2]);
					if(mask2==0) break;
				}
				dp[mask] += mi*1.0/F;
			}
		}
		
		return dp[(1<<B)-1];
		
	}
}

まとめ

O(4^N*M)だとTLが厳しいので、O(3^N*M)で解くテクを知っているかいないかという問題。