TopCoder SRM 577 Div1 Easy EllysRoomAssignmentsDiv1

さて久々のSRM通常回に参加。
…Easyを括弧の付け忘れでミスするというもったいないことをした。おかげで0完…。
ほんとSRMはミスが多くてレートが上がらない…。
http://community.topcoder.com/stat?c=problem_statement&pm=12514

問題

Ellyを含むTopCoder参加者のレート(整数値)がN人分(<=500)与えられる。
以下のルールで参加者をいくつかのRoomに分けるとき、Ellyがいる部屋の平均レートを答える。

• 各部屋は20人を超えない最大数、すなわち部屋数R=N/20+1またはN/20(Nが20で割り切れるとき)に分ける。
• レートを降順に並べ、最初のR人がR部屋にランダムに分けられ、次のR人がまたR部屋に分けられ…を繰り返す。

解法

「Ellyがいる」の判定は面倒なので、各部屋内でEllyと同じ順位がK番目の人、つまり全体で(KR+1)～(K+1)R番目の人をEllyと同じ得点にしてしまうとあとがラク。

後は以下の様に場合分けしていく。

Nが20の倍数の場合

どの部屋も割り当て人数が同じになるので、全員のスコアの平均を取るだけ。

Nが20の倍数ではない場合

N=P*R+Qとする。つまり、先頭のP*R人はP人ずつR部屋に割り当てて、最後に余ったQ(

• Ellyの順位が最後の余ったQ人に入る
  • この場合、Ellyの部屋は(P+1)人になる。よって(最初のP*R人の平均)×P人分とEllyの平均レートを取ればよい
• Ellyの順位が最後の余ったQ人に入らない
  • まず、(最初のP*R人の平均)を取り、そこからEllyの部屋に最後のQ人が入る場合と入らない場合の平均スコアをとってその平均を取ればよい。

class EllysRoomAssignmentsDiv1 {
	public:
	vector<int> split_int(const string &str, char delim){
		vector<int> res;
		size_t current = 0, found;
		while((found = str.find_first_of(delim, current)) != string::npos){
			string s = string(str, current, found - current);
			res.push_back(atoi(s.c_str()));
			current = found + 1;
		}
		string s = string(str, current, str.size() - current);
		res.push_back(atoi(s.c_str()));
		
		return res;
	}
	
	double getAverage(vector <string> ratings) {
		string s;
		int i;
		FOR(i,ratings.size()) s+=ratings[i];
		vector<int> rate=split_int(s,' ');
		int N=rate.size();
		int E=rate[0];
		int R=N/20+((N%20)?1:0);
		
		sort(rate.begin(),rate.end());
		reverse(rate.begin(),rate.end());
		int EI=-1;
		FOR(i,N) if(rate[i]==E) EI=i;
		FOR(i,N) if(EI/R==i/R) rate[i]=E;
		double r=0;
		int nc=0;
		
		if((N%20)==0) {
			FOR(i,N) r+=rate[i];
			r/=N;
		}
		else {
			int NPR=N/R;
			
			if(EI/R==N/R) {
				FOR(i,N/R*R) r+=rate[i];
				r = ((r/R)+E)/(NPR+1);
			}
			else {
				FOR(i,N/R*R) r+=rate[i];
				int NC=(N/R)*R;
				double tf=0;
				FOR(i,R) {
					if(i<(N%R)) {
						tf += ((r/R)+rate[i+(N/R)*R])/(NPR+1);
					}
					else {
						tf += (r/NC);
					}
				}
				r = tf/R;
			}
		}
		
		return r;
	}

};

まとめ

しょうもないチョンボで本番は損した。
「先にEllyと同順位の人のスコアをおなじにしておく」というアイデア、ほかには見かけなかったな。これはいいアイデアだと思うのだけど。