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

https://beta.atcoder.jp/contests/dwango2016-honsen/tasks/dwango2016final_b

問題概要

一次元上のN個の点を表す数列Xが与えられる。このうちのいずれかの点がオフィスだが、その点がオフィスであるかどうかは実際に訪れるまでわからない。ここで座標0からスタートし一定の速度vで一次元上を動き回るとき、どこにオフィスがあった場合でも必ずabs(Xi)以下の時間でオフィスにたどり着くようにしたい。最適な移動をしたとき取りうる最小の速度vを求めよ。

N <= 1000

abs(Xi) <= 109

解法

問題の二分探索臭がすごいので二分探索を考える。そうすると解くべき問題は「速度vを決め打つ。速度vで最適に動き回ったとき、Xのすべての点に時間abs(Xi)以下でたどり着くことは可能か」となる。ここで移動の特性を考えると

  • 点aから点bに移動したときa-b間にある点はすべてついでに取れる
  • このことから移動のパターンは「必ず外側が広がっていくようにジグザグに移動する」しかない(飛び地での移動も既に訪れた区間の内部をまた訪れるのも無意味)

ということがわかる。これを生かすと以下の区間DPが生える。

dp(i, j, left_or_right): 区間[X_i, X_j]を訪れていて、最後に訪れたのが(区間の左端or区間の右端)のときの、最小移動距離

上の特性からこのdpは外側に広がって区間を伸ばすような遷移しか考える必要がない。すなわち遷移は(左端or右端)×(左端or右端)の以下4パターンとなる。

  • X_i -> X_{i-1} (左端から左に一個進む)
  • X_i -> X_{j+1} (左端から右に折り返して右端を一個広げる)
  • X_j -> X_{i-1} (右端から左に折り返して左端を一個広げる)
  • X_j -> X_{j+1} (右端から右に一個進む)

遷移の際現在決め打っている速度で新たな点Xに時間abs(X)以内で到達できない場合は題意が満たされずその遷移は取れないのでスルーする。最後までDPを埋めたときdp(0, N-1)にちゃんと値が入っていればその速度はok, としてにぶたんを回していく。

感想

最後は必ず端っこで終わる→ひとつ前はその端っこの隣もしくは逆の端っこ→その繰り返し… となるとつまりジグザグが広がっていく形か~→それyukicoderでやったやつじゃんとなって区間DPが生えた。時間かかったけど通せて良かった~なお虚無の定数倍高速化(言語を変える)をまたやってしまいました

コード (C++)

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define REP2(i,m,n) for (int i=m;i<(n);i++)
typedef long long ll;
typedef long double ld;

ll X[1010];
ll dp[1010][1010][2];

bool in_time(int i, long dist, ld vel) {
    return dist / vel <= abs(X[i]);
}

int main() {
    const ll INF = 1L << 59;

    int N; cin >> N;
    REP(i, N) cin >> X[i];

    ld hi = 1000000000000000.0;
    ld lo = 1.0;

    REP(_, 100) {
        ld mid = (hi + lo) / 2;
        REP(i, N) REP(j, N) REP(k, 2) dp[i][j][k] = INF;
        REP(i, N) dp[i][i][0] = dp[i][i][1] = abs(X[i]);

        REP2 (len, 1, N+1) REP(l, N) REP(i, 2) REP(j, 2) {
            int r = l + len - 1;
            int nl = l;
            int nr = r;
            if (j == 0) nl -= 1;
            else        nr += 1;
            if (nl < 0 || nr >= N) continue;

            if (i == 0 && j == 0) {
                ll nd = dp[l][r][i] + X[l] - X[nl];
                if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
            } else if (i == 0 && j == 1) {
                ll nd = dp[l][r][i] + X[nr] - X[l];
                if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
            } else if (i == 1 && j == 0) {
                ll nd = dp[l][r][i] + X[r] - X[nl];
                if (in_time(nl, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
            } else if (i == 1 && j == 1) {
                ll nd = dp[l][r][i] + X[nr] - X[r];
                if (in_time(nr, nd, mid)) dp[nl][nr][j] = min(dp[nl][nr][j], nd);
            }
        }

        if (min(dp[0][N-1][0], dp[0][N-1][1]) != INF) hi = mid;
        else lo = mid;
    }

    cout.precision(20);
    cout << fixed  << hi << endl;
}