SRM557 Div1 Easy "EllysRoomAssignmentsDiv1"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12514
訳
エリーはプログラミングコンテストに参加する事にした。
コンテストが行われる前に、各参加者は部屋に振り分けられる(SRMのように)。
このコンテストは下記のようなアルゴリズムを使用して、
部屋の振り分けを行っている。
1. 参加者の数を N とする。 2. 部屋の数を R とすると、Nが20で割り切れるならば R = N / 20 そうでなければ R = N / 20 + 1とする。 3. 参加者を、レートにおいて非減少になるよう、ソートする。 4. まずR人の参加者を複数人を同じ部屋にしないよう、ランダムに部屋に配置する。 それから配置されてない参加者がいなくなるまで、 同じようにR人を配置していく。 最後のグループはR人より少ない場合があり、この場合も複数人が 同じ部屋に配置されないことに注意せよ。
あなたはStringの配列ratingsが与えられる。
まず、この配列の要素を連結させよ。
それは、スペースを区切り文字として、参加者のレートを表している。
このレートのリストには同じものは含まれていない。
エリーのレートはリストの最初のものである。
彼女が配置された部屋の、(彼女も含めての)レートの平均値の期待値を返せ。
制約
8 <= 参加者の数 <= 500
1200 <= 参加者のレート <= 3923
考えた事
でたよ期待値・・・
参加者 N が 20 で割り切れなければ、
余った参加者を振り分けるときに、配置される部屋とされない部屋がでてくる。
そして、エリーがその余りグループに入っていたら、
エリーが配置された部屋は
余りグループの参加者(つまりエリー自身)が必ず配置される部屋になるし、
そうでなければ (N % R) / R の確率で配置されることになる。
事後
なんとバグが発生せずに、ストレートでパスした。(奇跡)
苦手な期待値もだんだんと分かってきた・・か?
でも一時間ぐらいかかった。
ソースコード
class EllysRoomAssignmentsDiv1 { public: double getAverage(vector <string> ratings){ // レートのリストを作る string str; for( int i = 0; i < ratings.size(); i++ ){ str += ratings[i]; } istringstream iss( str ); vector<int> rs; int t; while( iss >> t ){ rs.push_back( t ); } int elly = rs[0]; // エリーのレート int N = rs.size(); // 参加者数 int R = N / 20 + (N % 20 ? 1 : 0); // 部屋数 int C = N / R + (N % R ? 1 : 0); // 振り分け回数 double rem_p = 0.0; // 余りグループがくる確率を出す if( N % 20 ) rem_p = (double)(N % R) / R; sort( rs.begin(), rs.end(), greater<int>() ); // 降順ソート // 合計値を出す double rem_p_sum = 0; double norem_p_sum = 0; for( int c = 0; c < C; c++ ){ int r_sum = 0; bool find = false; for( int i = 0; i < R && c * R + i < N; i++ ){ int id = c * R + i; if( rs[id] == elly ) find = true; r_sum += rs[id]; } // 余りグループだった if( c + 1 == C && N % R ){ // エリーがいた if( find ){ rem_p_sum = elly; rem_p = 1.0; // 余りグループは必ず配置される }else{ rem_p_sum = (double)r_sum / (N % R); } } // 余りグループではなかった else{ // エリーがいた if( find ){ norem_p_sum += elly; }else{ norem_p_sum += (double)r_sum / R; } } } double res = 0.0; // 余りを含めたもの / 余りを含めた人数 * 余りがくる確率 res += (norem_p_sum + rem_p_sum) / (N / R + 1) * rem_p; // 余りを含めないもの / 余りを含めない人数 * 余りがこない確率 res += norem_p_sum / (N / R) * (1.0 - rem_p); return res; } };