SRM462 Div1 Medium(450) CandyBox

CandyBox

箱の個数をnとすると、i回目の交換で箱jと箱kの飴が選ばれる確率はx=2(C/nC)(C/(nC-1))。交換前のそれぞれの箱の期待値をp, qとすると、箱jの期待値は(p-q)x/C増える。jもkも同じ箱が選ばれる確率はxではないけど交換に意味は無いので、まあいいか。

#include <vector>

using namespace std;

class CandyBox
{
public:
    vector <double> expectedScore( int C, vector <int> score, int S );
};

vector <double> CandyBox::expectedScore( int C, vector <int> score, int S )
{
    int n = (int)score.size();

    vector<double> s( score.begin(), score.end() );

    for ( int i=0; i<S; i++ )
    {
        vector<double> t = s;

        for ( int j=0; j<n; j++ )
        for ( int k=0; k<n; k++ )
            s[j] += ( t[k] - t[j] ) * 2*C/(n*C)/(n*C-1);
    }

    return s;
}