kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2018 Round3B Medium TestProctoring

勉強になりました。
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;
		
	}
}

まとめ

すごくシンプルな解法。