WARush

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

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