SRM577 Div2 Medium "EllysRoomAssignmentsDiv2"
問題
http://community.topcoder.com/stat?c=problem_statement&pm=12521
訳
エリーはプログラミングコンテストに参加する事にした。
コンテストが行われる前に、各参加者は部屋に振り分けられる(SRMのように)。
このコンテストは下記のようなアルゴリズムを使用して、
部屋の振り分けを行っている。
1. 参加者の数を N とする。 2. 部屋の数を R とすると、Nが20で割り切れるならば R = N / 20 そうでなければ R = N / 20 + 1とする。 3. 参加者を、レートにおいて非減少になるよう、ソートする。 4. まずR人の参加者を複数人を同じ部屋にしないよう、ランダムに部屋に配置する。 それから配置されてない参加者がいなくなるまで、 同じようにR人を配置していく。 最後のグループはR人より少ない場合があり、この場合も複数人が 同じ部屋に配置されないことに注意せよ。
あなたはStringの配列ratingsが与えられる。
まず、この配列の要素を連結させよ。
それは、スペースを区切り文字として、参加者のレートを表している。
このレートのリストには同じものは含まれていない。
エリーのレートはリストの最初のものである。
彼女が一番高いレーティングを持つ参加者と同じ部屋になる期待値を返せ。
制約
8 <= 参加者の数 <= 652
1 <= 参加者のレート <= 1199
考えた事
部屋が1つだけだと必ず一緒になる。
最初のグループだと必ず別になる。
それ以外なら1 / Rの確率で一緒になる。
事後
自分が最高レートなら必ず一緒になる処理入れ忘れ・・・
ソースコード
class EllysRoomAssignmentsDiv2 { public: double getProbability(vector <string> ratings){ // レートを入力 string str; for( int i = 0; i < ratings.size(); i++ ){ str += ratings[i]; } vector<int> rs; istringstream iss( str ); int t; while( iss >> t ){ rs.push_back( t ); } // 順位を出す int me = rs[0]; sort( rs.begin(), rs.end(), greater<int>() ); int num; for( int i = 0; i < rs.size(); i++ ){ if( rs[i] == me ){ num = i; break; } } int N = rs.size(); int R = N / 20 + (N % 20 != 0 ? 1 : 0); // 部屋が1だけ、もしくは自分が最高レートなら1.0 if( R == 1 || num == 0 ){ return 1.0; } // 自分が最初のグループなら0.0 if( num < R ){ return 0.0; }else{ return 1.0 / R; } } };