勉強になりました。
http://community.topcoder.com/stat?c=problem_statement&pm=14766
問題
N人の人がテストを受ける。
i番目の人は1秒毎にp[i]の確率でテストに合格しテストから抜ける。
全員がテストから抜けるまでの時間の期待値を求めよ。
解法
f(i) := i秒目の段階で未合格の人がいる確率
とすると、求める解はf(1)+f(2)+...となる。
ここで、f(i)は包除原理の要領で、2^N通りの項の加減算で求めることができる。
この時、f(1), f(2), ...における各項の値は等比数列を成すので、2^N通りの項それぞれでその和を求めればよい。
class TestProctoring { public: double expectedTime(vector <int> p, vector <int> q) { vector<double> D; int N,i; N=p.size(); FOR(i,N) D.push_back(1.0*p[i]/q[i]); double ret=0; for(int mask=1;mask<1<<N;mask++) { double left=1; FOR(i,N) if(mask&(1<<i)) left*=(1-D[i]); if(__builtin_popcount(mask)%2==0) ret-=1/(1-left); else ret+=1/(1-left); } return ret; } }
まとめ
すごくシンプルな解法。