TopCoder SRM 370 Div1 Easy DrawingMarbles
問題概要
入れ物の中に入っている、それぞれの色のマーブルが何個ずつかが与えられる。
入れ物からマーブルをn個引くとき(一度引いたマーブルは戻さない)、引いたマーブルが全て同じ色である確率を求めよ。
解法
それぞれの色をn個引く確率を足し合わせれば良い。
その色のマーブルがn個以上あれば組み合わせから確率を求め、n個未満だったら飛ばす。
ソースコード
class DrawingMarbles { public: double sameColor(vector <int> colors, int n) { int m=colors.size(),sum=accumulate(all(colors),0); double ans=0; rep(i,m)if(colors[i]>=n) { ans+=C(colors[i],n)/C(sum,n); } return ans; } double C(int n,int k) { double ret=1; rep(i,k)ret*=n-i,ret/=i+1; return ret; } };