AIM Tech Round : D. Birthday

類題を解いていたはずなのに頭から抜けていた…そもそも本番Bで苦戦してここまでまともに読めてなかった。
http://codeforces.com/contest/623/problem/D

問題

N人の人がうろついている。
プレイヤーは目隠しをしてうろついている１人に声を掛け、その人が誰かを推測する。
その際各人に声を掛ける確率はP[i]である(sum(P)=1である)。
プレイヤーは結局その人が誰であるかはずっとわからない。

この条件の元、プレイヤーが最適な順番で推測を行うとき、平均何回推測を行うと、初めて全員１回以上推測を当てた状態となるか期待値を求めよ。

解法

以下類題である。
yukicoder : No.210 探し物はどこですか？ - kmjp's blog

x回目までにi番目の人を当てた確率をF(x,i)とする。
全員を1回以上当てた確率prod_i(F(x,i)) = G(x)とすると、求めたいのはx*(G(x)-G(x-1))である。
(初めて全員当てたタイミングを求めたいので、(x-1)回以前に当てた確率を引いている。)

するとG(x)をできるだけ早く大きくするような推測を行うのが良いこととなる。
G(x)はF(x,i)の積なので、１回推測を行うとF(x,i)の増加率が最大となる場所を選ぶのが良い。

x回目にi番の人を選ぶとき、F(x,i) = F(x-1,i) + (1-F(x-1,i))*P[i]となる。
よってi番目の人を選ぶことでG(x)は(1-F(x-1,i))*P[i]/F(x-1,i)倍に増えることになる。
この値が最大なものを適宜選べばよい。
実際はF(x-1,i)は初期では0なので、除算を避けて比較しよう。
Priority Queueで上記倍率が最大のものを管理してもよいが、N人総当たりしても問題ない。

あとは、上記処理を10^6回目位までシミュレートしよう。
ここまで来るとF(x,i)は皆1に近くなっており、これ以上の影響は誤差の範囲内に収まる。

int N;
double P[101];
long double did[101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>P[i], P[i]/=100;
	
	long double ret=0;
	long double predid=0;
	for(i=1;i<=1000000;i++) {
		int best=0;
		for(x=1;x<N;x++) if((1-did[x])*P[x]*did[best]>did[x]*(1-did[best])*P[best]) best=x;
		
		did[best] += (1-did[best])*P[best];
		long double newdid=1;
		FOR(x,N) newdid*=did[x];
		ret += i*(newdid-predid);
		predid=newdid;
	}
	_P("%.12lf\n",(double)ret);
	
}

まとめ

せっかくyukicoderで得たテクだったのに、頭から抜けてた…。