AtCoder ARC #016 : C - ソーシャルゲーム

苦手意識の強い期待値問題。
部分点稼ぎで無駄にWAを重ねてしまったが、最終的に解けたのでよかった。
http://arc016.contest.atcoder.jp/tasks/arc016_3

問題

N人のアイドルカードがある。
M種類のくじがあり、各くじをcost[i]払って１つ引くと、idol[i][1]～idle[i][C[i]]までのカードのいずれかがP[i][1]～P[i][C[i]の確率で手に入る。

最適手を取ってくじを選択するとき、N人分そろうまでのコストの期待値を求めよ。

解法

N<=10なのでBitDPで解いていくとよい。
現在のカードの所持状態をbitmaskで表現し、各bitmaskから初めて全カードをそろえるまでの期待値E(mask)を順に求めればよい。
全bitが埋まった状態からだんだんbitを減らす方向でBitDPしていく。

ここであるbitmaskについて、M種類の各くじを引いた場合の期待値を計算し、最小値をとる。
各くじを引いた際の期待値は下記の通り計算できる。

• このくじを引いて得られるカードを全て所持しているなら、このくじを引くのは無駄なのでスキップする。
• そうでない場合、すでに持っているカードを引く確率はidol[i][j]がbitmaskに含まれるようなjにおいてP[i][j]の和をとった値Qである。
• よって、まだ持っていないカードを引くまでのコストはcost[i]*(1+Q+Q^2+Q^3+...)=cost[i]/(1-Q)。
• まだ持っていないカードidol[i][j]に対し、E(mask) += P[i][j]/(1-Q) * [ E(mask | (1＜＜idol[i][j])) + cost[i]/(1-Q) ] を求めればよい。

int N,M;
int C[101];
int cost[101];
int I[101][101];
int P[101][101];

double dpdp[2048];

void solve() {
	int f,i,j,k,l, x,y;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>C[i]>>cost[i];
		FOR(j,C[i]) cin>>I[i][j]>>P[i][j];
		FOR(j,C[i]) I[i][j]--;
	}
	
	FOR(i,1<<N) dpdp[i]=1e300;
	dpdp[(1<<N)-1]=0;
	
	for(int mask=(1<<N)-2;mask>=0;mask--) {
		FOR(i,M) {
			double t;
			int al=0;
			FOR(j,C[i]) if(mask & (1<<I[i][j])) al+=P[i][j];
			if(al==100) continue;
			t=cost[i]*100.0/(100-al);
			
			FOR(j,C[i]) {
				if(mask & (1<<I[i][j])) continue;
				t += P[i][j]/(100.0-al)*dpdp[mask | (1<<I[i][j])];
			}
			
			dpdp[mask] = min(dpdp[mask],t);
		}
	}
	_P("%.8f\n",dpdp[0]);
}

まとめ

少しは期待値問題に慣れてきたかな…。