問題
http://community.topcoder.com/stat?c=problem_statement&pm=4487&rd=7220
４種類の絵柄のトランプあり、それぞれの絵柄についてカード数が与えられる。
Ｎ枚のカードを引いたとき、最も多い同じ絵柄のカード数がFlushスコアになる。
このとき、Flushスコアの期待値を求める。
解き方
カードの種類は４種類、カード数は１３枚なので、
あり得る全てのカードの取り方について全探索すればよい。
コード
#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 Flush {
public:
double f(int x,int y){
double ret=1.0;
for(int i=y;i>y-x;i--)ret*=i;
for(int i=x;i>0;i--)ret/=i;
return ret;
}
double size(vector<int> s, int number) {
double ret=0.0;
FORE(i,0,s[0]+1){
FORE(j,0,s[1]+1){
FORE(k,0,s[2]+1){
FORE(l,0,s[3]+1){
if(i+j+k+l!=number)continue;
int len=max(i,max(j,max(k,l)));
double p=f(i,s[0])*f(j,s[1])*f(k,s[2])*f(l,s[3]);
ret+=len*p;
}
}
}
}
return ret/f(number,s[0]+s[1]+s[2]+s[3]);
}
};
#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 Flush {
public:
double f(int x,int y){
double ret=1.0;
for(int i=y;i>y-x;i--)ret*=i;
for(int i=x;i>0;i--)ret/=i;
return ret;
}
double size(vector<int> s, int number) {
double ret=0.0;
FORE(i,0,s[0]+1){
FORE(j,0,s[1]+1){
FORE(k,0,s[2]+1){
FORE(l,0,s[3]+1){
if(i+j+k+l!=number)continue;
int len=max(i,max(j,max(k,l)));
double p=f(i,s[0])*f(j,s[1])*f(k,s[2])*f(l,s[3]);
ret+=len*p;
}
}
}
}
return ret/f(number,s[0]+s[1]+s[2]+s[3]);
}
};