Google Code Jam 2017 Round 1C : C. Core Training

理屈はまだしっかり理解していないので、解き方だけ。
https://code.google.com/codejam/contest/3274486/dashboard#s=p2

問題

N個の処理があり、それぞれ成功確率はP[i]である。
P全体を合計Uだけ上昇させることができる。
N個中K個以上の処理が成功する確率を最大化せよ。

解法

N=Kの場合

この場合全処理を成功させる必要があり、その確率はprod(P)である。
どこかの処理の成功確率をΔpだけ増やしてprod(P)をできるだけ大きくしたいが、その場合元のP[i]が最小のものを増やすのが最も効率が良い。
よって、Pの最小値が最大となるようにしよう。

これはPの最小値を二分探索してもよいし、Pのうち複数最小値のものがあれば均等にUを振り分けていってもよい。

N!=Kの場合

Editorialに細かい理屈は書いてあるが、後半まだ理解できていない(特にi≧i0のあたり)ので、他の解法のうちシンプルなもののみ紹介。
なんでこれでうまくいくかはしっくりこない。
N個中K個成功すればいいので、もともと成功確率が低すぎるものにUを割り振るよりは、もう少し確度の高いものに割り振った方が良い場合がある。

よって以下のようにする。

• Pのうち大きないくつかを上限1にするように割り振る
• Pのうち小さないくつかを切り捨て、残りの要素に対しN=Kの時同様に最小値を底上げする

1にする要素数と切り捨てる要素数を総当たりし、それぞれの確率の最大値を求めるとよい。
O(N^4)と少し重いがC++なら十分間に合う。

int N,K;
double U;
double P[101],Q[101];
double L[101][101];

void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	cin>>N>>K>>U;
	FOR(i,N) cin>>P[i];
	sort(P,P+N);
	
	double ma=0;
	for(k=N-1;k>=0;k--) {
		FOR(i,N) {
			FOR(j,N) Q[j]=P[j];
			double l=0,r=1;
			FOR(j,100) {
				double m=(l+r)/2;
				double left=U;
				for(x=i;x<N;x++) left-=max(0.0,m-Q[x]);
				if(left<0) r=m;
				else l=m;
			}
			
			for(x=i;x<N;x++) Q[x]=max(Q[x],l);
			ZERO(L);
			L[0][0]=1;
			FOR(x,N) {
				FOR(y,N) {
					L[x+1][min(K,y+1)] += L[x][y]*Q[x];
					L[x+1][y] += L[x][y]*(1-Q[x]);
				}
			}
			ma=max(ma,L[N][K]);
		}
		
		double a=min(1-P[k],U);
		P[k]+=a;
		U-=a;
	}
	if(U>0) ma=1;
	
	_P("Case #%d: %.12lf\n",_loop,ma);
}

まとめ

LargeではなくSmall2にしたってことは、色々実験で試すのが想定だったのかな。