WARush

SRMの結果とか、解けた問題のコードを書いていきます

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;
        }
    }
};