第2回 ドワンゴからの挑戦状 本選 B - 道迷い

問題

dwango2016-honsen.contest.atcoder.jp

解法

速度 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;
}