kmjp's blog

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

Codeforces #253 Div1 B. Andrey and Problem

細かい理屈を判断せず、推測で通してしまった。
http://codeforces.com/contest/442/problem/B

問題

N人の友人がいる。
彼らは、依頼するとp[i]の確率で来てくれる。

友人のうち何人かに依頼し、ちょうど1人だけやってくる確率を最大化せよ。

解法

p[i]をソートし、そのうち一部連続区間を総当たりして、1人だけやってくる確率を求めればよい。
上記手法ではO(N^3)で最大化できる。

本番、これで良い理由は深く考えず通してしまった。
Editorialに証明があるので、興味があるならそちらを見ると良い。

別解法としては、やってくる確率の高い順に、まだやってくる確率が増える限り選択する、という手法もある。
この場合、ソートにかかるO(N*logN)で解ける。

int N;
double P[101];

double dodo(int L,int R) {
	double fail=1,ma=0;
	int i;
	for(i=L;i<R;i++) fail*=1-P[i];
	for(i=L;i<R;i++) ma+=fail/(1-P[i])*P[i];
	return ma;
}

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		if(P[i]==1) return _P("1.0\n");
	}
	
	sort(P,P+N);
	double ma=0;
	FOR(x,N) for(y=x+1;y<=N;y++) ma=max(ma,dodo(x,y));
	_P("%.12lf\n",ma);
}

まとめ

結構な正答者がいるけど、まじめに証明した人は少なさそう。