第2回 ドワンゴからの挑戦状 本選 B - 道迷い
解法
速度 v に対して二分探索します。
check(v) = (速度 v で足りるかどうか) というのは, dp で確かめることが出来ます。
dp[l][r][rflag] = (区間 [l, r] は既に到達済みという状態になるための最短時間(rflag = 0 なら l に, rflag = 1 なら r にいる))
という dp を考えます。すると, x[pos] = 0 として, dp[pos][pos][0] = dp[pos][pos][1] = 0 です。また, dp[l][r][rflag] の遷移は,
- l < pos なら, dp[l][r][0] は [l+1, r] の区間から左側に移動することになるので, min(dp[l+1][r][0] + abs(x[l+1]-x[l])/v, dp[l+1][r][1] + abs(x[r]-x[l])/v)
- r > pos なら, dp[l][r][1] は [l, r-1] の区間から右側に移動することになるので, min(dp[l][r-1][0]+abs(x[r]-x[l])/v, dp[l][r-1][1]+abs(x[r]-x[r-1])/v)
t = dp[l][r][0] の値は, t <= abs(x[l]) が成り立ってないと, 怒られることになるので, t > abs(x[l]) なら dp[l][r][0] = INF にしておきましょう。check(v) は min(dp[0][N-1][0], dp[0][N-1][1]) < INF なら true です。
const int MAXN = 1010; double INF = 1e12; double dp[MAXN][MAXN][2]; vector<int> x; int N, pos; bool check(double v) { for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { dp[i][j][0] = dp[i][j][1] = INF; } dp[pos][pos][0] = dp[pos][pos][1] = 0; for (int w = 2; w <= N; w++) { for (int l = max(pos-w+1, 0); l <= pos; l++) { int r = l+w-1; if (r >= N) continue; if (l < pos) { for (int i = 0; i < 2; i++) { int prev = i ? r : l+1; double t = dp[l+1][r][i]; t += abs(x[l]-x[prev])/v; if (t <= abs(x[l])) dp[l][r][0] = min(dp[l][r][0], t); } } if (r > pos) { for (int i = 0; i < 2; i++) { int prev = i ? r-1 : l; double t = dp[l][r-1][i]; t += abs(x[r]-x[prev])/v; if (t <= abs(x[r])) dp[l][r][1] = min(dp[l][r][1], t); } } } } if (min(dp[0][N-1][0], dp[0][N-1][1]) > INF/2) return false; return true; } int main() { cin >> N; { vector<int> tmp(N); for (int i = 0; i < N; i++) { cin >> tmp[i]; } bool flag = false; for (int i = 0; i < N; i++) { if (tmp[i] > 0 && !flag) { flag = true; x.push_back(0); pos = x.size()-1; } x.push_back(tmp[i]); } if (!flag || pos == 0) { cout << 1 << endl; return 0; } N = x.size(); } double low = 1, high = 1e10; for (int i = 0; i < 100; i++) { const double med = (high+low)/2; if (check(med)) high = med; else low = med; } printf("%.12lf\n", (high+low)/2); return 0; }