yukicoder : No.574 正多面体サイコロ

すんなり解けてよかった。
https://yukicoder.me/problems/no/574

問題

正F面体のサイコロがあり、各面1～Fの整数が１つずつ書かれている。
このサイコロをN回ころがし、出た値を大きい順に並べたとき、K番目に来る値の期待値を求めよ。

解法

K番目に1～Fが来る確率をそれぞれ求めよう。

K番目にある値xが来るには、xより大きい値がK回未満、xより小さい値が(N-K)回以下だけ出ればよい。
N回中xより大きい値がa回、xより小さい値がb回出る確率はなので、a,bを総当たりしつつ確率の総和を求めればよい。

int F,N,K;
double fact[102];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	fact[0]=1.0;
	FOR(i,101) fact[i+1]=fact[i]*(i+1);
	
	cin>>F>>N>>K;
	double ret=0;
	for(i=1;i<=F;i++) {
		double prob=0;
		double A=(i-1.0)/F;
		double B=1.0/F;
		double C=1.0*(F-i)/F;
		
		FOR(x,N-K+1) FOR(y,K) {
			prob += pow(A,x)*pow(B,N-x-y)*pow(C,y)*(fact[N]/fact[x]/fact[y]/fact[N-x-y]);
		}
		
		ret += i*prob;
	}
	_P("%.12lf\n",ret);
}

まとめ

欲しい値より大きいか小さいか等しいかの３つに分類するのがコツ。