細かい理屈を判断せず、推測で通してしまった。
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); }
まとめ
結構な正答者がいるけど、まじめに証明した人は少なさそう。