問題
http://community.topcoder.com/stat?c=problem_statement&pm=12514&rd=15497
解き方
部屋の数Rから、部屋への割り当てが行われる回数Kが決まる。
K回の割り当てのうち、
自分が割り当てられる場合はその他のメンバーは関係なく、
また最後の割り当てのときはすべての部屋ではなく、ランダムに部屋へ割り当てられるので別に値を保持しておく。
最後に、自分が最後の割り当てであれば部屋の人数はK人だけを考えればよく、
そうでなければK-1人となる確率pの期待値とK人である1-pの期待値の和が答えとなる。
コード
class EllysRoomAssignmentsDiv1 {
public: double getAverage(vector<string> ratings) {
int rates[1010],N=0;
string input=accumulate(all(ratings),string());
stringstream out(input);
for(;out>>rates[N];)N++;
int my=rates[0];
sort(rates,rates+N,greater<int>());
int me=lower_bound(rates,rates+N,my,greater<int>())-rates;
int R=(N+19)/20;
int K=(N+R-1)/R;
double sum=0,add=0;
for(int i=0;i<K;i++){
if(R*i<=me && me<R*(i+1)){
sum+=rates[me];
}else if(i==K-1){
double tmp=0.0;
for(int j=R*i;j<N;j++)tmp+=rates[j];
add+=tmp/(N-R*i);
}else{
double tmp=0.0;
for(int j=R*i;j<R*(i+1);j++)tmp+=rates[j];
sum+=tmp/R;
}
}
double p=(R*K-N)/(double)R;
if(R*(K-1)<=me)p=0;
double ret=0;
if(p>0)ret+=p*(sum/(K-1));
ret+=(1-p)*((sum+add)/K);
return ret;
}
};
public: double getAverage(vector<string> ratings) {
int rates[1010],N=0;
string input=accumulate(all(ratings),string());
stringstream out(input);
for(;out>>rates[N];)N++;
int my=rates[0];
sort(rates,rates+N,greater<int>());
int me=lower_bound(rates,rates+N,my,greater<int>())-rates;
int R=(N+19)/20;
int K=(N+R-1)/R;
double sum=0,add=0;
for(int i=0;i<K;i++){
if(R*i<=me && me<R*(i+1)){
sum+=rates[me];
}else if(i==K-1){
double tmp=0.0;
for(int j=R*i;j<N;j++)tmp+=rates[j];
add+=tmp/(N-R*i);
}else{
double tmp=0.0;
for(int j=R*i;j<R*(i+1);j++)tmp+=rates[j];
sum+=tmp/R;
}
}
double p=(R*K-N)/(double)R;
if(R*(K-1)<=me)p=0;
double ret=0;
if(p>0)ret+=p*(sum/(K-1));
ret+=(1-p)*((sum+add)/K);
return ret;
}
};