SRM462 Div1 Medium(450) 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; }