Codeforces 261 B Maxim and Restaurant

問題

n人の人がいて、それぞれの人の大きさはa[i]である。
n人はn!通りの並び方を等しい確率で選んで並ぶ。
大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。
入る人が、入れない人を飛ばすことはできない。

レストランに入れる人数の期待値を求めよ。

制約条件

n≦50
p≦50

方針

最初にレストランに入れなくなる人を決めうち。

入れない人をi番目の人とすると、入れる人の大きさの和はp - a[i]〜a[i]なので、
i番目の人以外でDPをして、
dp[入れる人数][大きさ和] := 場合の数
を求める。
これで、p - a[i]〜a[i]の和に対して、入れる人数 * (入れる人数)! * (入れない人数)! * 場合の数 / n!
を期待値に足せばいい。

ソースコード

int n, a[50], p;
double dp[51][2501], f[100];
double calc(int e){
	memset(dp, 0, sizeof(dp));
	dp[0][0] = 1;
	
	rep(i, n) if(i != e) for(int j = n - 1; j >= 0; j--)
	for(int k = 2500; k >= 0; k--) if(dp[j][k]){
		dp[j + 1][k + a[i]] += dp[j][k];
	}
	double res = 0;
	rep(i, n) for(int j = max(0, p - a[e] + 1); j <= p; j++){
		if(!dp[i][j]) continue;
		//cerr<<"i: "<<i<<" j: "<<j<<" dp: "<<dp[i][j]<<endl;
		res += i * dp[i][j] * f[i] * f[n - 1 - i];
	}
	//cerr<<"e: "<<e<<" res: "<<res<<endl;
	return res;
}
int main(){
	f[0] = 1;
	rep(i, 99) f[i + 1] = f[i] * (i + 1);
	
	cin >> n;
	rep(i, n) cin >> a[i];
	cin >> p;
	
	int s = 0;
	rep(i, n) s += a[i];
	if(s <= p){
		cout << n << endl;
		return 0;
	}
	
	double res = 0;
	rep(i, n) res += calc(i);
	printf("%.9f\n", res / f[n]);
	
	return 0;
}