問題
http://community.topcoder.com/stat?c=problem_statement&pm=6116&rd=9814
１セットあたりのゲーム回数が与えられ、それを指定回数分のセット数行う。
１ゲームにたいして勝つ確率が与えられ、そのセット数で勝つために必要な勝ちゲーム数が与えられる。
このとき、少なくとも１つのセットで勝つことのできる確率を求める。
解き方
問題文の理解に少し時間がかかった。
１セットあたりに負ける確率さえ計算できれば、答えは１－負ける確率＾セット数で求められる。
１セットあたりに負ける確率の計算に順列を使ってもよいが、
ゲーム数は２０なので全探索してもたかだか１０＾６程度なので間に合う。
コード
class ScrabbleBet {
public: double estimate(int trials, int games, int winsNeeded, int winChance) {
double loses=0.0;
double p=winChance/100.0;
for(int i=0;i<(1<<games);i++){
int x=0;
for(int j=0;j<20;j++)if(i&(1<<j))x++;
if(x<winsNeeded)loses+=pow(p,x)*pow(1.0-p,games-x);
}
return 1.0-pow(loses,trials);
}
};
public: double estimate(int trials, int games, int winsNeeded, int winChance) {
double loses=0.0;
double p=winChance/100.0;
for(int i=0;i<(1<<games);i++){
int x=0;
for(int j=0;j<20;j++)if(i&(1<<j))x++;
if(x<winsNeeded)loses+=pow(p,x)*pow(1.0-p,games-x);
}
return 1.0-pow(loses,trials);
}
};
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 ScrabbleBet {
public:
double C(int a,int b){
double ret=1.0;
FORE(i,0,b)ret*=(double)(a-i)/(1+i);
return ret;
}
double estimate(int trials, int games, int winsNeeded, int winChance) {
double p=0.0;
double winp=winChance/100.0;
FORE(i,winsNeeded,games+1){
p+=C(games,i)*pow(winp,i)*pow(1.0-winp,games-i);
}
return 1.0-pow(1.0-p,trials);
}
};
#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 ScrabbleBet {
public:
double C(int a,int b){
double ret=1.0;
FORE(i,0,b)ret*=(double)(a-i)/(1+i);
return ret;
}
double estimate(int trials, int games, int winsNeeded, int winChance) {
double p=0.0;
double winp=winChance/100.0;
FORE(i,winsNeeded,games+1){
p+=C(games,i)*pow(winp,i)*pow(1.0-winp,games-i);
}
return 1.0-pow(1.0-p,trials);
}
};