TopCoder SRM 543 Div2 Hard EllysThreeRivers

正月なのでDiv2 Hardを延々解いています。
http://community.topcoder.com/stat?c=problem_statement&pm=11911

問題

幾何問題なのでサイト上の図を見るとよい。
プレイヤーは初期状態で座標(0,0)にいる。そこに３つの川が流れており、幅はW[0],W[1],W[2]で、X座標が0～W[0]、W[0]～(W[0]+W[1])、(W[0]+W[1])～(W[0]+W[1]+W[2])の部分が川に相当する。
また、X座標が0,W[0],(W[0]+W[1]),(W[0]+W[1]+W[2])の部分は幅が0だが地面がある。

(0,0)から(W[0]+W[1]+W[2],L)に最短時間で移動したい。
陸路の移動速度walkと、各川の移動速度S[i]が与えられたとき、最短時間を示せ。

解法

陸路はそれぞれの川の間で移動しても、最初原点で移動しても最終的な移動時間は同じである。
よって、陸路分は最初(0,0)から(0,H[0])に移動し、残りは陸路は移動せず３つの川を(W[0],H[0]+H[1]),(W[0]+W[1],H[0]+H[1]+H[2]),(W[0]+W[1]+W[2],L)と渡ることを考える。

まずH[0]+H[1]を固定してPとする。
すると(W[0],P)を経由する移動時間はとなる。

よって答えはf(P)=f(g(H[0])+h(H[2]))となる。
関数f,g,hはいずれも下に凸なグラフとなるため、以下では二分探索ならぬ四分探索で最小値を求めていく。
探索1回で3/4に探索範囲を狭めるので、100ループ位すれば精度も十分である。

class EllysThreeRivers {
	public:
	int L,WA;
	vector<int> W,S;
	
	double len1(double le) {
		int x;
		double l=0,r=le,res=0;
		FOR(x,100) {
			double p0=(l+r)/2.0;
			double p1=(l+p0)/2.0;
			double p2=(r+p0)/2.0;
			
			double lp0=p0/WA+sqrt(W[0]*W[0]+(le-p0)*(le-p0))/S[0];
			double lp1=p1/WA+sqrt(W[0]*W[0]+(le-p1)*(le-p1))/S[0];
			double lp2=p2/WA+sqrt(W[0]*W[0]+(le-p2)*(le-p2))/S[0];
			
			if(lp1==lp2) l=p1,r=p2;
			else if(lp1<lp2) r=p2;
			else l=p1;
			res=min(lp0,min(lp1,lp2));
		}
		
		return res;
	}
	
	double len2(double le) {
		int x;
		double l=0,r=le,res=0;
		FOR(x,100) {
			double p0=(l+r)/2.0;
			double p1=(l+p0)/2.0;
			double p2=(r+p0)/2.0;
			
			double lp0=sqrt(W[1]*W[1]+p0*p0)/S[1]+sqrt(W[2]*W[2]+(le-p0)*(le-p0))/S[2];
			double lp1=sqrt(W[1]*W[1]+p1*p1)/S[1]+sqrt(W[2]*W[2]+(le-p1)*(le-p1))/S[2];
			double lp2=sqrt(W[1]*W[1]+p2*p2)/S[1]+sqrt(W[2]*W[2]+(le-p2)*(le-p2))/S[2];
			
			if(lp1==lp2) l=p1,r=p2;
			else if(lp1<lp2) r=p2;
			else l=p1;
			res=min(lp0,min(lp1,lp2));
		}
		
		return res;
	}
	
	double getMin(int length, int walk, vector <int> width, vector <int> swim) {
		L=length;
		WA=walk;
		W=width;
		S=swim;
		
		double l=0,r=length,res=0;
		int x;
		
		FOR(x,100) {
			double p0=(l+r)/2.0;
			double p1=(l+p0)/2.0;
			double p2=(r+p0)/2.0;
			
			double lp0=len1(p0)+len2(length-p0);
			double lp1=len1(p1)+len2(length-p1);
			double lp2=len1(p2)+len2(length-p2);
			
			if(lp1==lp2) l=p1,r=p2;
			else if(lp1<lp2) r=p2;
			else l=p1;
			res=min(lp0,min(lp1,lp2));
		}
		
		return res;
	}
};

まとめ

想定解は偏微分解くのかな？と思ったけどやはりEditorialを見ると探索のようだ。