天下一プログラマーコンテスト2016本戦 : F - Blind Purchase

だいぶ前の問題だけど、公式解説がないので残しておく。
https://tenka1-2016-final-open.contest.atcoder.jp/tasks/tenka1_2016_final_f

問題

N種類のアイテムをそれぞれ１個ずつ以上買い揃えることを考える。
アイテムを買うには以下のいずれかの手順がある。

• 金額Gを支払うと、N種のいずれかが等確率で手に入る。
• 金額P[i]を払うと、i番目のアイテムが手に入る。

両者の入手方法を任意に行える場合、全アイテムをそろえるまでの金額の期待値を求めよ。

解法

現在持っているアイテムについて、2^N通り状態を列挙できれば容易に解けそうだが、あいにくNが最大36と大きいのでそうもいかない。
一方気になるのはG,Pが小さいことである。

まず、最適手を考える。
前者の購入手段でアイテムを買う方が、後者で買うより低コストであることが期待できる間は前者がよい。
そうでなくなった瞬間、残りは後者の手順で買い揃えるのが良い。

初期状態でG*N≧sum(P)の場合、最初からすべて後者の手順で揃えるのが良いので、その場合は解は明らか。
そうでない場合、どこかで前者から後者に戦略を切り替えるタイミングがある。
このタイミングと、その状態に至る確率を列挙することを考えよう。

S=sum(P)とし、D=sum(すでに入手済みアイテムのP[i])とする。
前者では、G支払うことで、平均コスト(S-D)/N相当のリターンが得られることになる。
よってG＜(S-D)/Nの間は前者を継続するのがよい。言い換えると、D≧S-G*Nとなった瞬間に後者の手順に切り替えることになる。

前者を繰り返し、i番を入手する直前はD＜S-G*Nで、i番を入手した瞬間D+P[i]≧S-G*Nとなるケースを列挙しよう。
i番を総当たりしていく。
その際、i番以外の要素について、以下を求めよう。これはO(N^2*sum(P))で求められる。
f(n,k) := (N-1)個中n個が入手済みで、そのP[i]の総和がkとなるような組み合わせ
kが[S-G*N-P[i], S-G*N-1]の範囲の場合、i番目のアイテムをn+1個目として入手すると後者の戦略に切り替えることになる。
前者の戦略を繰り返し、アイテムの入手順がそうなるのはf(n,k)/(n+1)/C(N,n+1)である。

よって、*1 * f(n,k) / (n+1) / C(N,n+1)をすべて足し合わせればよい。

int N,G;
int P[36];

const int CN=40;
double C[CN][CN];
ll dp[37][37][37*37];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,CN) for(j=0;j<=i;j++) C[i][j]=(j==0||j==i)?1:(C[i-1][j-1]+C[i-1][j]);
	
	cin>>N>>G;
	int sum=0;
	FOR(i,N) cin>>P[i], sum+=P[i];
	if(sum<=N*G) return _P("%d\n",sum);
	
	double ret=0;
	FOR(i,N) {
		ZERO(dp);
		dp[0][0][0]=1;
		FOR(j,N) FOR(x,N) FOR(y,36*36) if(dp[j][x][y]) {
			dp[j+1][x][y]+=dp[j][x][y];
			if(j!=i) dp[j+1][x+1][y+P[j]]+=dp[j][x][y];
		}
		
		double cost=0;
		FOR(x,N) {
			cost+=1.0*G*N/(N-x);
			FOR(y,37*37) if(dp[N][x][y] && y<sum-N*G && y+P[i]>=sum-N*G) {
				ret+=(cost+(sum-y-P[i]))*(dp[N][x][y]/C[N][x+1]/(x+1));
			}
		}
	}
	_P("%.12lf\n",ret);
	
}

まとめ

コードこそ短いけど、このDPは思いつけないわ…。

*1:前者の戦略で(n+1)個揃える金額の期待値) + (S-(k+P[i]