SRM 543 500pt : EllysRivers

問題概要

(0,0)から(N,L)(N<50, L<10^5)への最短路が知りたい。(i,j)->(i,j+1)へは1.0/vで移動でき、(i,j)->(i+1,j+k)へはsqrt(w[i]^2 + k^2)/u[i]で移動できる。

解法

とりあえずO(L^2*N)の自明なDPが見える。本番中はこれを落とせないか考えていたけど落とせなかった。終了後Petr先生の解答見て勉強した。
上に1つ移動するときにどこを使うべきかを毎回貪欲に最も良いものから選べば良い。最良のものを選ぶのにheapなどを使うとO(L*log(N))で解けるけど線形探索でO(L*N)となり十分間に合う。
しゃくとりっぽくO(L*N)で解いている人も多かったけれど、なぜそれで上手くいくのか未だに理解できてないしコンテスト中に思いついてさらに納得するのは自分には多分無理っぽい。

acceptされたコード

#include <vector>
#include <cmath>
#include <numeric>
using namespace std;

const int MAX_N = 50;

double hs[MAX_N];
double ts[MAX_N], nts[MAX_N];

struct EllysRivers {

	double sq(double x){
		return x * x;
	}

	double getMin(int L, int v, vector<int> ws, vector<int> us) {
		double ans = 0.0;
		const int N = ws.size();
		for(int i=0; i<N; ++i){
			hs[i] = 0.0;
			ts[i] = sqrt(sq(ws[i]) + 0) / us[i];
			nts[i] = sqrt(sq(ws[i]) + 1) / us[i];
		}

		for(int _=0; _<L; ++_){
			double best = 1.0 / v;
			int key = -1;
			for(int i=0; i<N; ++i){
				if(nts[i] - ts[i] < best){
					best = nts[i] - ts[i];
					key = i;
				}
			}

			if(key != -1){
				ts[key] = nts[key];
				hs[key] += 1.0;
				nts[key] = sqrt(sq(ws[key]) + sq(hs[key] + 1.0)) / us[key];
			}
			else{
				ans += 1.0 / v;
			}
		}

		ans += accumulate(ts, ts+N, 0.0);
		return ans;
	}

};