問題
http://community.topcoder.com/stat?c=problem_statement&pm=10071&rd=13509
ｎ個のくじからm個選ぶ。
相手も同様にm個選ぶ。
選んだくじのうち、相手がえらんだくじとk個一致していれば勝ちとなる。
このとき、勝ちとなる確率を求める。
解き方
ｎが８と小さいので、全探索すればよいだけ。
コード
class TwoLotteryGames {
public: double getHigherChanceGame(int n, int m, int k) {
double ret=0.0,sum=0.0;
for(int i=1;i<1<<n;i++)if(__builtin_popcount(i)==m){
for(int j=1;j<1<<n;j++)if(__builtin_popcount(j)==m){
sum++;
if(__builtin_popcount(i&j)>=k)ret++;
}
}
return ret/sum;
}
};
public: double getHigherChanceGame(int n, int m, int k) {
double ret=0.0,sum=0.0;
for(int i=1;i<1<<n;i++)if(__builtin_popcount(i)==m){
for(int j=1;j<1<<n;j++)if(__builtin_popcount(j)==m){
sum++;
if(__builtin_popcount(i&j)>=k)ret++;
}
}
return ret/sum;
}
};