TopCoder SRM 543 Div1 Medium EllysRivers

Div2 Hardのアレンジ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11912

問題

基本設定はDiv2 Hardと似ている。
TopCoder SRM 543 Div2 Hard EllysThreeRivers - kmjp's blog

ただしこちらは川を移動するボートの始点終点が整数座標でなければならない。
また、川が３つでなくN本ある。

解法

Div2 Hardはボートの始点終点の座標が実数値だったが、こちらは整数値のためDPすればよい。
ただ、始点終点の座標を持って愚直にDPするとO(N*Length^2)ありTLEする。

自分は、DPの際ボートの終点を定めたとき、距離が最短となる始点を三分探索で求めた。
定数倍高速化を頑張ると何とか2sでギリギリ間に合う。

Editorialによると、隣接する終点のDPでは、答えとなる始点も近距離にあることが期待できるため、それによってDPの探索範囲を大幅に減らすことができるようだ。

double dpdp[51][100001];
double tim[100001];
ll L,R;
class EllysRivers {
	public:
	int N;
	
	double dodo(int cur,ll pos) {
		R=min(R,pos);
		L=max(L-1,0LL);
		while(R-L>=9) {
			ll po1=(L*2+R)/3;
			ll po2=(L+R*2)/3;
			double h1=dpdp[cur][po1]+tim[pos-po1];
			double h2=dpdp[cur][po2]+tim[pos-po2];
			if(h1==h2) L=po1,R=po2;
			else if(h1<h2) R=po2;
			else L=po1;
		}
		
		double hoge=1e20;
		for(ll x=L;x<=R;x++) hoge=min(hoge,dpdp[cur][x]+tim[pos-x]);
		return hoge;
	}
	
	double getMin(int length, int walk, vector <int> width, vector <int> speed) {
		N=width.size();
		int i,x,y;
		ZERO(dpdp);
		FOR(i,length+1) dpdp[0][i]=i/(double)walk;
		
		FOR(x,N) {
			FOR(i,length+1) tim[i]=sqrt(width[x]*(ll)width[x]+i*(ll)i)/(double)speed[x];
			R=length;
			L=0;
			for(i=length;i>=0;i--) dpdp[x+1][i]=dodo(x,i);
		}
		return dpdp[N][length];
	}
}

まとめ

頑張って定数倍高速化で通ったけど、本番この手を取るのは危険だな…。