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;
	}
};