SRM626に参加。
せっかくEasyをそこそこの時間で解いたのに、しょうもないミスで落としてしまいレート激減…。
http://community.topcoder.com/stat?c=problem_statement&pm=13239
http://community.topcoder.com/stat?c=problem_statement&pm=13240
問題
2人でサイコロを振って、目の総和を競う。
先手は1~aの目を持つa面サイコロをb個振る。
後手は1~cの目を持つc面サイコロをd個振る。
先手の総和が後手を上回るとき、先手の総和の期待値を求めよ。
なお、Div2 Mediumはサイコロ数b,dが1である。
解法
まず先手後手DPで各総和が出る確率を求める。
先手の総和xに対し、その先手を取る確率をP(x)、後手がx未満の総和を取る確率をQ(x)とする。
総和xをP(x)*Q(x)で重みづけして期待値を取ればよい。
Div2 Mediumはサイコロの数が1つであり、各目が出る確率は均一なのでだいぶコードを簡略化できる。
class FixedDiceGameDiv1 { public: double dp[2][2602]; double getExpectation(int a, int b, int c, int d) { int x,y,z,i; if(a*b<=c) return -1.0f; ZERO(dp); dp[0][0]=dp[1][0]=1; FOR(x,a) { for(y=a*b;y>=0;y--) if(dp[0][y]) { FOR(z,b) dp[0][y+z+1]+=dp[0][y]/(double)(b); dp[0][y]=0; } } FOR(x,c) { for(y=c*d;y>=0;y--) if(dp[1][y]) { FOR(z,d) dp[1][y+z+1]+=dp[1][y]/(double)(d); dp[1][y]=0; } } double ret=0,ho=0; FOR(i,2501) { double tt=0; FOR(x,i) tt+=dp[1][x]; ret+=i*dp[0][i]*tt; ho+=dp[0][i]*tt; } if(ho==0) return -1.0f; return ret/ho; } } class FixedDiceGameDiv2 { public: double getExpectation(int a, int b) { int x,y; int tot=0,num=0; for(x=1;x<=a;x++) for(y=1;y<=min(x-1,b);y++) num++,tot+=x; return tot/(double)num; } }
まとめ
ミスがしょうもなさ過ぎて残念すぎる。