SRM 422 DIV1 Easy - PrimeSoccer (復習○)
問題
http://community.topcoder.com/stat?c=problem_statement&pm=10033&rd=13513
・チームＡとＢがサッカーゲームを行う。
・ゲームは９０分あり、５分ごと、１８回のセグメントに分けられる。
・各セグメントごと、各チームはあらかじめ与えられた確率でゴールする。
・各セグメントごとのゴール数は０か１となる。
このとき、ゲームが終わったときＡもしくはＢのスコアが素数となる確率を求める。
解き方
２＾３６となるので全探索では解くことができない。
ここで、最大が１８なので素数の数は７個に限られる。
次に、ゴール数をｎ、Ａのゴールする確率がＰのときの確率は
P^n * (1-P)^(18-n)*18Cnとなる。
最後に、Aの素数となる確率とＢの素数となる確率で重複が発生する。
Aのゴール数が素数となる確率をPa、Ｂのゴール数が素数となる確率をPbとすると
Pa+Pb-Pa*Pbが答えになる。
コード
class PrimeSoccer {
public:
double calc(double x){
int p[]={2,3,5,7,11,13,17};
double ret=0.0;
FORE(i,0,7){
double tmp=1.0;
for(double n=18.0;n>(double)(18-p[i]);n--)tmp*=n;
for(double n=1.0;n<=(double)p[i];n++)tmp/=n;
tmp=tmp*pow(x,p[i])*pow(1.0-x,18-p[i]);
ret+=tmp;
}
return ret;
}
double getProbability(int skillOfTeamA, int skillOfTeamB) {
double Pa=calc((double)skillOfTeamA/100.0);
double Pb=calc((double)skillOfTeamB/100.0);
return Pa+Pb-Pa*Pb;
}
};
public:
double calc(double x){
int p[]={2,3,5,7,11,13,17};
double ret=0.0;
FORE(i,0,7){
double tmp=1.0;
for(double n=18.0;n>(double)(18-p[i]);n--)tmp*=n;
for(double n=1.0;n<=(double)p[i];n++)tmp/=n;
tmp=tmp*pow(x,p[i])*pow(1.0-x,18-p[i]);
ret+=tmp;
}
return ret;
}
double getProbability(int skillOfTeamA, int skillOfTeamB) {
double Pa=calc((double)skillOfTeamA/100.0);
double Pb=calc((double)skillOfTeamB/100.0);
return Pa+Pb-Pa*Pb;
}
};
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 PrimeSoccer {
public:
double calc(double p){
int x[]={0,1,4,6,8,9,10,12,14,15,16,18};
double ret=0.0;
FORE(i,0,12){
double num=1;
for(int j=0;j<x[i];j++)num*=(double)(18-j)/(j+1);
ret+=num*pow(p,x[i])*pow(1.0-p,18-x[i]);
}
return ret;
}
double getProbability(int skillOfTeamA, int skillOfTeamB) {
double PA=calc((double)skillOfTeamA/100.0);
double PB=calc((double)skillOfTeamB/100.0);
return 1.0-PA*PB;
}
};
#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 PrimeSoccer {
public:
double calc(double p){
int x[]={0,1,4,6,8,9,10,12,14,15,16,18};
double ret=0.0;
FORE(i,0,12){
double num=1;
for(int j=0;j<x[i];j++)num*=(double)(18-j)/(j+1);
ret+=num*pow(p,x[i])*pow(1.0-p,18-x[i]);
}
return ret;
}
double getProbability(int skillOfTeamA, int skillOfTeamB) {
double PA=calc((double)skillOfTeamA/100.0);
double PB=calc((double)skillOfTeamB/100.0);
return 1.0-PA*PB;
}
};
