mayoko’s diary

プロコンとかいろいろ。

SRM 543 div1 med: EllysRivers

TopCoder
問題

TopCoder Statistics - Problem Statement

地点(0, 0) から 地点(n, L) まで移動したい。ただし, 地点 (i, y) と地点 (i+1, y) は距離 w[i] だけ離れている。
移動の仕方としては 2 通りの移動の仕方がある。

  • (i, l1) から (i, l2) まで速度 walk で歩いて移動
  • (i, l1) から (i+1, l2) まで速度 s[i] で移動

ここで, l1, l2, i はすべて整数でなければならない。
地点(0, 0) から 地点(n, L) まで移動するのにかかる最短時間を求めよ。

解法

まだサンプルが通ることしか確かめてないです。通りました。また, 解説見たんですが完璧に理解したとは言えないです。

dp[i][l] = (地点(i, l) に到達するための最短時間) という dp が思い浮かびます。遷移は,

dp[i][p] = min(dp[i+1][q]+sqrt((q-p)^2+w[i]^2)/s[i]) (p <= q <= L) です。

ただこれを普通に実装しても O(nL^2) になるので間に合いません。

で, ここで dp[i+1][q] + sqrt((q-p)^2+w[i]^2)/s[i] が凸になることを利用します(凸になる理由がイマイチわかりません)。


凸になることを考えると, O(nLlogL) になりますが, これも計算量的に怪しい(無理と解説には書いてある)のでもう少し改良します。

実は, dp[i][p] を最小にする遷移の元が q であった場合, dp[i][p-1] を最小にする遷移の元が q より大きくなることがないことがわかります。これと凸であることを合わせると, 次のような O(nL) 解法が妥当であるとわかります。

dp[tar][j] = dp[cur][pos] + sqrt(1.*(j-pos)*(j-pos) + 1.*w[i]*w[i])/s[i];
while (pos >= j && pos > 0) {
    double next = dp[cur][pos-1] + sqrt(1.*(j-pos+1)*(j-pos+1) + 1.*w[i]*w[i])/s[i];
    if (dp[tar][j] > next) {
        dp[tar][j] = next;
        pos--;
    } else break;
}

上記の性質が成り立つ理由ですが,

O(x, y), A(x+1, y1), B(x+1, y2), C(x+2, y3), D(x+2, y4) という点を考えます。(y <= y1 < y2 <= y3 < y4)

ここで, O -> D に行く時は O -> A -> D と行くのが最適で, O -> C に行く時は O -> B -> C と行くのが最適であるとすると,
OA*s + AC*r > OB*s + BC*r (C に行くルートの長さの比較)
OA*s + AD*r < OB*s + BD*r (D に行くルートの長さの比較)
となりますが, 両辺を足すと (AC+BD)*r > (BC+AD)*r i.e. AC+BD > BC+AD となり, これは明らかに矛盾しているので, 上記の性質が成り立つことがわかります。

double dp[2][100010];

class EllysRivers {
public:
    double getMin(int L, int walk, vector <int> w, vector <int> s) {
        int n = w.size();
        for (int i = 0; i < 2; i++) for (int j = 0; j <= L; j++) dp[i][j] = 1e9;
        int cur = 0;
        for (int i = 0; i <= L; i++) dp[0][i] = 1.*(L-i) / walk;
        for (int i = n-1; i >= 0; i--) {
            int tar = cur^1, pos = L;
            for (int j = 0; j <= L; j++) dp[tar][j] = 1e9;
            for (int j = L; j >= 0; j--) {
                dp[tar][j] = dp[cur][pos] + sqrt(1.*(j-pos)*(j-pos) + 1.*w[i]*w[i])/s[i];
                while (pos >= j && pos > 0) {
                    double next = dp[cur][pos-1] + sqrt(1.*(j-pos+1)*(j-pos+1) + 1.*w[i]*w[i])/s[i];
                    if (dp[tar][j] > next) {
                        dp[tar][j] = next;
                        pos--;
                    } else break;
                }
            }
            cur = cur^1;
        }
        return dp[cur][0];
    }
};