TopCoder SRM 543 Div1 Medium EllysRivers

問題

xy平面上に、n本の川とn+1個の陸地がある。
i番目の川の幅はwidth[i]で、n番目の陸地とn+1番目の陸地の間を流れている。
その川を渡るときのスピードは、speed[i]（方向によらず一定）である。

陸地は細長く、y軸に平行な線分とみなすものとする。
線分の下側の端点のy座標は0, 上側の端点のy座標はlengthである。
陸地の、座標が整数の点には船着場がある。

(0, 0)を出発して、陸地を歩くか、船を使い、n+1番目の陸地のy座標lengthの点へ移動したい。
陸地を歩くスピードはwalkである。船の出発点と到着点は船着場である必要がある。
移動にかかる最短時間を求めよ。

制約条件

n≦50
length≦100000
speed[i]≦100000
width[i]≦100000

方針

DP.
更新を全部やろうとするとTLEなので、計算量を落とす必要がある。

最小値を三分探索で見つけようとすると、ギリギリTLEするっぽい。
なので、しゃくとり的にやる。
dp[i][j] = min{dp[i-1][k] + dist[k - j]}を最小にするkは、
jを動かしたときに、常に右にずれていくので、
前のjから出発して右にdp[i-1][j] + dist[k - j]が減少する間kを増やしてやればいいことがわかる。

なんでdp[i-1[k] + dist[k - j]の最小値が右にずれていくかは、dp[i - 1][k]とdist[k - j]のグラフを考えたらわかる。
dp[i - 1][k]はkについて単調増加な関数。
dist[k - j]は、k = jのとこで最小値を取る下に凸な関数。
これが、jが増えると、distだけが右にずれるので、最小値を取るkは右にずれる。

ソースコード

double dp[60][100010];

class EllysRivers {
	public:
	double getMin(int length, int walk, vector <int> width, vector <int> speed) 
	{
		int n = width.size();
		rep(i, 60) rep(j, 100010) dp[i][j] = INF;
		dp[0][0] = 0;
		for(int k = 1; k <= n; k++){
			for(int i = 0, j = 0; i <= length; ){
				double a = dp[k - 1][j]     + hypot(width[k - 1], j - i )    / speed[k - 1];
				double b = dp[k - 1][j + 1] + hypot(width[k - 1], j + 1 - i) / speed[k - 1];
				if(a <= b) dp[k][i++] = a;
				else j++;
			}
		}
		double ans = INF;
		rep(i, length + 1) ans = min(ans, dp[n][i] + 1.0 * (length - i) / walk);
		return ans;
	}
};