kmjp's blog

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

AtCoder ARC #034 : D - インフレゲーム

うーむ、自力で完答まで行かなかった。
http://arc034.contest.atcoder.jp/tasks/arc034_4

問題

A+B+Cの計N枚のカードがある。

  • A枚はそれぞれ赤字で整数a[i]が書かれている。
  • B枚はそれぞれ青字で整数b[i]が書かれている。
  • C枚は湯たんぽが描かれている。

このN枚を偏りなくシャッフルし、1枚ずつカードを取っていく。その際:

  • 赤字の整数が書かれたカードを取ったら、自分の得点がカードの数値分加算される
  • 青字の整数が書かれたカードを取ったら、自分の得点がカードの数値分乗算される
  • 湯たんぽが描かれたカードを取ったら、その場でゲーム終了。

ゲーム終了時の得点の期待値を答えよ。

解法

全探索しようとすると(A+B)!通りほど探索空間があるので部分点が精いっぱい。
そこで何とか探索空間を減らすことを考える。

まず赤字のカードについて考える。
実はこの問題はa[i]の個々の値を考慮する必要はなく、1回赤字のカードを引いたらa[i]の平均値の分スコアが増えると考えればよい。
ゲーム終了まで、M回赤字カードが出たとする。
i回目の赤字カードの番号をP[i]とし、Q[i]を以降ゲーム終了までに取った青字カードの数値の積とする。
するとゲーム終了時のスコアはa[P[i]]*Q[i]の総和となる。
P[i]がそれぞれどの値になるかは1/Aの確率であり、よってa[P[i]]の期待値はa[i]の期待値と一致する。
そのため以後個別のa[P[i]]は考えず、a[i]の平均値で考えてよい。

一方Q[i]は単純に青字の平均値を取るわけではない。
Q[i]がbのうちx枚取ったときの期待値とすると、(bのうちx枚取ったときの積の総和)/(b枚中x枚の選び方)の式で平均を取る必要がある。
前者は簡単なDP、後者は単なるCombinationである。

ここまでで、「1枚赤字を引いたときの平均値」「x枚青字を引いたときの総倍率」までが求まった。
後は状態を(残り赤字枚数,残り青字枚数)としてメモ化再帰で得点を計算していけば良い。

int A,B,C,T;
int VA[100],VB[100];
double bdp[52];
double memo[55][55];
const int CN=51;
ll Co[CN][CN];
double AA;

double dp(int TA,int TB) {
	if(memo[TA][TB]>=0) return memo[TA][TB];
	double pa=TA*1.0/(TA+TB+C);
	double pb=TB*1.0/(TA+TB+C);
	double ret=0;
	if(pa) ret += pa*(bdp[B-TB] + dp(TA-1,TB));
	if(pb) ret += pb*dp(TA,TB-1);
	return memo[TA][TB]=ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C;
	FOR(i,A) cin>>VA[i], AA+=VA[i];
	FOR(i,CN) for(j=0;j<=i;j++) Co[i][j]=(j==0||j==i)?1:(Co[i-1][j-1]+Co[i-1][j]);
	FOR(i,51) FOR(j,51) memo[i][j]=-1;
	
	bdp[0]=1;
	FOR(i,B) {
		cin>>VB[i];
		for(j=50;j>=0;j--) bdp[j+1]+=bdp[j]*VB[i];
	}
	for(i=1;i<=B;i++) bdp[i]=bdp[i]/Co[B][i];
	
	_P("%.12lf\n",dp(A,B)*(AA/A));
}

まとめ

a[i]は相加平均を取るので、最初b[i]は相乗平均かと思って盛大にミスした。