SRM577 Div1 Easy - EllysRoomAssignmentsDiv1

くだらねえ問題

問題

プログラミングコンテストにn人の参加者がいて、i人目のレートはa[i]である
コンテストの部屋の個数rは r = ceil(n/20) とする
まず参加者をレートの降順に並べ、その後各参加者を順番にr人ずつ見ていき、そのr人それぞれが互いに異なる部屋に入るようにランダムに部屋に入れる
降順ソートする前の0番目の人の部屋のレーティングの平均値の期待値を求めよ

8 <= n <= 500
1200 <= a[i] <= 3923

解法

(0番目の人の名前はElly)
r人ずつ配っていくとn%r(=kとする)人だけ余る
この余りにEllyが含まれる場合は同じ部屋の人数はn/r+1人で確定
そうじゃない場合はn/r人の場合とn/r+1人の場合がある
書いててダルくなったから以下略

class EllysRoomAssignmentsDiv1 {
public:
	double getAverage(vector<string> s) {
		string t;
		each(i,s) t += i;
		vector<double> a;
		for (int i=0; i<t.size(); i+=5) a.push_back(stoi(t.substr(i,4)));
		int n = a.size(), r = (n+19)/20, k = n%r, cnt = n/r;
		double x = a[0];
		sort(a.rbegin(), a.rend());
		int id = find(all(a), x) - a.begin();
		for (int i=0; i<r*cnt; i+=r) {
			if (i<=id && id<i+r) continue;
			rep(j,r) x += a[i+j]/r;
		}
		if (r*cnt<=id) return x/(cnt+1);
		double res = x/cnt*(r-k)/r;
		reps(i,r*cnt,n) res += (x+a[i])/(cnt+1)/r;
		return res;
	}
};

https://community.topcoder.com/stat?c=problem_statement&pm=12514&rd=15497