SRM 577

250

自分の部屋にいる人のレーティングの平均の期待値を求める問題です。

与えられる文字列を連結する。

部屋の数R = (n+20-1)/20
であり、(n-1)%R+1 人が最後に部屋分けされる。(このとき、1つの部屋に振り分けられる人数は20よりだいぶ小さくなることもある。)

の2つが分かれば、少し実装が大変ですが解けます。

int r[3000];

class EllysRoomAssignmentsDiv1{
public:
	double getAverage(vector <string> s) {
		int n = 0;
		memset(r,0,sizeof(r));
		
		string s2;
		for(int i = 0; i < s.size(); i++)s2 += s[i];
		stringstream ss(s2);
		while(ss>>r[n++]);//この方法で入力すると、nが1つ余計に多くなることに注意する
		if(!r[n-1])n--;
		
		int R = (n+19)/20;
		int me = r[0],mne;
		bool last = false;
		sort(r,r+n,greater<int>());
		for(int i = 0; i < n; i++)if(r[i]==me)mne = i;
		if(mne/R==(n-1)/R)last = true;
		int ex = (n-1)%R+1;
		
		double a = 0.0,b = 0.0;
		int sum = 0;
		for(int i = 0; i < n; i++){
			if(!(i%R)){
				a += (double)sum/R;
				sum = 0;
			}
			if(i/R!=mne/R) sum += r[i];
		}
		b = (double)sum/ex;
		
		int num = (n+R-1)/R;
		if(last) return (a+me)/num;
		else return (a+me)/(num-1)*(R-ex)/R+(a+me+b)/num*ex/R;
 	}
};

--- 0

1456 -> 1412