うーむ、自力で完答まで行かなかった。
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]は相乗平均かと思って盛大にミスした。