SRM 626 DIV1 Easy - FixedDiceGameDiv1 (×)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=13239&rd=15859
・AliceとBobでゲームを行う。
・Aliceはa個b面あるサイコロを投げ、Bobはc個d面あるサイコロを投げる。
・b面あるサイコロは1～bの数字が書かれており、d面あるサイコロは1～dの数字が書かれている。
・Aliceが勝った時、出た目の期待値を求める。
・Aliceが勝つケースがないときは-1を返す。
解き方
・まずAliceが勝つかどうか判定する。
・Bobの一番小さい数はcであるので、c+1以上の面が出るときに勝つことができる。
・次にAliceの勝つ面について、どれだけの確率があるか計算する。
・dpを用いればできそう。
・現在までに使ったサイコロの数、現在までの合計のスコアを持つdpを作れば
場合の数は計算できる。
・確率として、勝つ面が出た時のすべての場合の数の和を取り、最後に割ってあげる。
・サンプルはすべて通った。
→System Failed
・Aliceだけの面をみていたが、Bobの面も見る必要がある。
・つまり、Aliceの勝つ数についての場合の数＊Bobがそれに負けるときの場合の数を足してあげ、
その和を全てとり最後に割ってあげる必要がある。
・反省：確率の問題に弱い・・・。基礎が足りないのを実感。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FixedDiceGameDiv1 {
public: double getExpectation(int a, int b, int c, int d) {
double dp1[a+1][2501],dp2[c+1][2501];
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
dp1[0][0]=dp2[0][0]=1;
FORE(i,0,a)FORE(j,0,2501)FORE(k,1,b+1)if(j+k<=a*b)dp1[i+1][j+k]+=dp1[i][j];
FORE(i,0,c)FORE(j,0,2501)FORE(k,1,d+1)if(j+k<=c*d)dp2[i+1][j+k]+=dp2[i][j];
double ret=0.0,sum=0.0;
FORE(i,c+1,a*b+1){
double p=0.0;
FORE(j,0,i)p+=dp2[c][j];
ret+=i*dp1[a][i]*p;
sum+=dp1[a][i]*p;
}
return ret ? ret/sum : -1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class FixedDiceGameDiv1 {
public: double getExpectation(int a, int b, int c, int d) {
double dp1[a+1][2501],dp2[c+1][2501];
memset(dp1,0,sizeof(dp1));
memset(dp2,0,sizeof(dp2));
dp1[0][0]=dp2[0][0]=1;
FORE(i,0,a)FORE(j,0,2501)FORE(k,1,b+1)if(j+k<=a*b)dp1[i+1][j+k]+=dp1[i][j];
FORE(i,0,c)FORE(j,0,2501)FORE(k,1,d+1)if(j+k<=c*d)dp2[i+1][j+k]+=dp2[i][j];
double ret=0.0,sum=0.0;
FORE(i,c+1,a*b+1){
double p=0.0;
FORE(j,0,i)p+=dp2[c][j];
ret+=i*dp1[a][i]*p;
sum+=dp1[a][i]*p;
}
return ret ? ret/sum : -1;
}
};
