kojingharangの日記

SRM 577 Div1 250 EllysRoomAssignmentsDiv1

02:59 |

• rating を持つ N 人でコンテストをやる。それぞれどこかの部屋に割り当てられる。部屋数 R = (N+19)/20
• rating の降順にソートした後 R 人ずつ部屋が重複しないように割り当てていく。
• ソート前の最初の人の部屋の rating 平均値の期待値を求める問題。
• 8≦N≦500
• 1200≦rating[i]≦3923

• 期待値うげーー

• 線形性うんたらでどれがどれだけ寄与するか足していけば良いのだろう
• N が R で割り切れない場合ややこしそう
• 部屋の人数が N/R の場合と N/R+1 の場合で各 rating がどれだけ寄与するか式とか図で考える
• 期待値とはみたいな
• きりが良いときは ( (?+?+?)/?人 + (?+?+?)/?人 + ...全部で[R^部屋の人数]項... ) / R^部屋の人数
• = Σrating / R / 人数 みたいな

• きりが良くない場合も考えると
• (最初の人の)部屋の人数が N/R 人になる確率、そうでない確率が分かるので、人数別の期待値にそれぞれ掛け合わせる感じ

• R 個ずつグループ化して、最初の人が含まれるときはその rating, それ以外は rating[i]/グループの人数 が寄与する
• ほとんどのサンプルがちょっとずつ合わない

• ソートするの見落としてた
• 最初の人がソートした後何番目にくるかとか考えないといけないじゃんよ

• ほとんどのサンプルがちょっとずつ合わない

• おわり

• （あとで）

• 最初の人がソートした後最後のはしたグループに来る時だけ特別っぽくて、そのときは部屋の人数は N/R+1 人と確定してるので N/R 人の期待値は足さない。
• それ以外は上記の考え方でよさげ

• 変数名がアレゲ
• 最近 easy ができません

• Accepted in practice room

class EllysRoomAssignmentsDiv1 {
	public:
	double getAverage(vector <string> RS) {
		string s;
		FOR(e, RS) s+=*e;
		VI w;
		stringstream ss(s);
		int v;
		while(ss>>v) w.PB(v);
		int me = w[0];
		sort(ALLR(w));
		//cout<<w<<endl;
		int N = w.size();
		int ORE=0;
		REP(i, N) if(me==w[i]) ORE=i;
		int R = (N+19)/20;
		cout<<"R "<<R<<endl;
		cout<<"me "<<me<<endl;
		cout<<"ore "<<ORE<<endl;
		double ans = 0;
		double ext = 0;
		int p1 = N-N/R*R;
		double ooi = (double)p1 / R;
		cout<<"p1 "<<p1<<" "<<N/R<<" "<<endl;
		for(int i=0;i<N;i+=R) {
			int NUM = min(R, N-i);
			if(i/R==ORE/R) {
				ans += me;
				continue;
			}
			if(NUM==R) {
				REP(j, NUM) {
					ans += (double)w[i+j] / NUM;
				}
			} else {
				REP(j, NUM) {
					ext += (double)w[i+j] / NUM;
				}
			}
		}
		if((N-1)/R==ORE/R && p1) {
			return (ans+ext) / (N/R+1);
		} else {
			return (1.0-ooi) * ans / (N/R)  +  ooi * (ans+ext) / (N/R+1);
		}
	}
};

ツイートする