Codeforces #277.5 Div2 E. Hiking

これ系の問題苦手…。
http://codeforces.com/contest/489/problem/E

問題

初期状態で座標0にいる。
N個のポイントがあり個々の座標はX[i]で、そこに停止した際の満足度はB[i]である。

ポイント間を座標が増える方向に移動する際、１回で距離をr移動すると定数Lに対しストレスが√|r-L|たまる。
最終的にN個目のポイントX[N-1]に到達したい。

その際、相対的なストレス、すなわちストレスの和を停止したポイントの満足度の和で割ったときの値を最小化するような停止ポイントを答えよ。

解法

止まるポイントをS[0]、S[1]、…、S[M-1]=N-1とする。
さらに１回の移動距離をR[i]=X[S[i]]-X[S[i-1]]とする。

仮に求める最小値をmとする。するとSの選択順を問わず、
(√|D[0]-L|+√|D[1]-L|+...+√|D[M-1]-L|)/(B[S[0]]+B[S[1]]+...+B[S[M-1]])≧m
となる。イコールとなるのは答えを最小化できる停止ポイントである。

上記式を変形すると、
(√|D[0]-L|+√|D[1]-L|+...+√|D[M-1]-L|)≧m*(B[S[0]]+B[S[1]]+...+B[S[M-1]])
(√|D[0]-L|-m*B[S[0]]) + (√|D[1]-L|-m*B[S[1]]) + ... (√|D[M-1]-L|-m*B[S[M-1]]) ≧ 0
となる。

よって、mの候補を二分探索し、(√|D[i]-L|-m*B[S[i]])の和が最小となるようO(N^2)のDPを行う。
和がマイナスとなる場合、mが大きすぎるので、さらに小さなmを求めることができる。

このような最適値を仮置きしつつ二分探索していく方法は、過去にも登場している。
AtCoder ARC #016 : D - 軍艦ゲーム - kmjp's blog

int N,L;
ll X[1050],B[1050];

double cost[1001][1001];
double mi[1001];
int mif[1001];

void solve() {
	int i,j,k,x,y; string s;
	
	cin>>N>>L;
	FOR(i,N) cin>>X[i+1]>>B[i+1];
	N++;
	FOR(x,N) for(y=x+1;y<N;y++) cost[x][y]=sqrt(abs(X[y]-X[x]-L));
	
	vector<int> V;
	double l=0,r=1e10;
	FOR(i,100) {
		double m=(l+r)/2;
		for(x=1;x<N;x++) {
			mif[x]=-1;
			mi[x]=1e10;
			FOR(y,x) {
				double co=cost[y][x]-m*B[x];
				if(mi[x]>=mi[y]+co) mi[x]=mi[y]+co, mif[x]=y;
			}
		}
		
		if(mi[N-1]<0) {
			r=m;
			V.clear();
			x=N-1;
			while(x!=0) V.push_back(x), x=mif[x];
		}
		else {
			l=m;
		}
	}
	
	reverse(V.begin(),V.end());
	ITR(it,V) _P("%d ",*it);
	_P("\n");
}

まとめ

本番二分探索まではたどり着いたが、どう式変形するか絞りきれなかった。