Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-06-04

[][] TopCoder SRM 543 Div.1 Level2 (500) EllysRivers 00:01 はてなブックマーク -  TopCoder SRM 543 Div.1 Level2 (500) EllysRivers - 練習帳

問題文

 問題文

概要

  • 複数の川が平行に並んでいて、川と川の間には直線の道路がある。川の幅は川ごとに異なる。
    • つまり2次元座標を適当に置くと、川はy軸に平行な帯状領域で、道路はy軸に平行な直線と思える。以降この座標系を用いる
  • 川と道路を移動する事で、左下のスタート地点(0, 0)から右上のゴール地点(W, L)まで移動したい。そのために要する最短時間を求めよ。
  • 川内では自由な方向に移動できるが、道路は細いためy軸方向のみ移動できる。
    • 道路を移動する速度はすべての道路で共通だが、川内を移動する速度は川ごとに異なる。
  • 川から道路への移動と道路から川への移動はy座標が整数の点でのみ行える。
    • スタート、ゴール地点は共に道路上の点
  • 制限:
    • 川の数(以下ではNと書く)は50以下、川と道路での移動速度は10**6以下、それぞれの川の幅は10**6以下でL, Wは整数で10**6以下

コード

 Practiceでの提出コード(gist):https://gist.github.com/2793235

考えた過程

問題を簡単にする

まず、道路を移動するスピードはどこでも同じなので、徒歩での移動するのは一番右端の道路でのみ行うことにします。本当にこの簡単化が効果的かはわかりませんが、とりあえずやっておきます。

動的計画法なのはすぐわかるけれど

dp[i][a]を、i番目の川を渡り終え、y座標がaの位置に達するのに要する最短時間とします。dp[i][*]達からdp[i+1][*]達が計算でき、また求めるべき答えはdp[N][L]なのでこのdpを更新する動的計画法で答えが求まります。しかし、問題なのはdpの更新をナイーブに行うと時間がかかってしまう点です。dp[i+1][y]は、y以下の非負整数aに対してdp[i][a]+(aからyまで川を移動する)を計算し、その最小値を取れば計算できます。しかし、この方法ではdp[i+1][*]達の計算にはO(L**2)です。Lが10**6程度なので、1回の更新だけでも制限時間を超えてしまいます。

高速の高速化を考える

そこで、この更新をもっと速くできないかと考えます。自分が探した範囲だと少なくとも2通りの方法が有りました。1つ目の方法は最小値を達成できない可能性を分割統治法を用いて枝狩りし、2つ目の方法は目的関数の凸性を用いて探索範囲を狭めています。最初に挙げた自分の提出コード(と入っても他の方の回答のほぼ丸写しですが...)は前者の方法を用いています。以下ではその方法を解説します。

後で良く使うので、以下の記号を用います。

  • i:以下の文脈では定数と思います
  • dp[i][a]:i番目の川を渡り終えて、y座標がaの位置に達するまでに要する最短時間
  • f(a, b) = 川の左端でy座標がaの点から、右端でbの点まで泳ぐのに要する時間。
    • つまり、dp[i+1][y]はf(a, y)をaの変数と見た時の最小値です。
  • a-bライン:川の左端でy座標がaの地点から、川の右端でy座標がbの地点までを結んだ直線
更新の高速化

y座標が丁度真ん中の点、つまりdp[i+1][L/2]を計算した結果、f(y, L/2)の最小値をy=a0で達成したとします。すると、次のことがわかります:「左端がy ∈ [0, a0]の地点から右端がz ∈ [L/2, L]の地点に泳いで移動する方法ではdp[i+1][z]の最小値を達成できない」。つまり今L/2に到達するために泳いだ直線を横切るような泳ぎ方は最適ではありません。これの証明は後で行います。

同様にして、a0-L/2のラインを逆向きに横切る方法(つまり、川の左端でy座標がy ∈ [a, L]の点からから川の右端でy座標がz ∈ [0, L/2]に移動する方法)も最適な経路でないことがわかります。すると、dp[i][L/2]を計算してしまえば、後は[0, a]→[0, L/2]の移動と[a, L]→[L/2, L]の移動だけを調べれば十分となります。つまり、分割統治法です。

証明

以下の事を証明します: 「dp[i+1][y] = min_{b} dp[i][b]+f(b, y) の最小値がb=aで達成される時、b < a、y < zとなるb, zに対して、dp[i][a]+f(a, z) < dp[i][b]+f(b, z)が成立する」

(証明)

dp[i][y]の最小値を取る経路の中にb-yラインを泳ぐ経路も含まれているので、dp[i+1][y] = dp[i][a]+f(a, y) ≦ dp[i][b]+f(b, y) が成立します。これと証明したい式を見比べると、f(b, y)-f(a, y) < f(b, z)-f(a, z) ・・・(※)を示せば十分です。

fは具体的な式でわかっていて、 f(a, y) = sqrt( (y-a)**2+w**2)/sです。ここで、sqrtは平方根、wは川幅、sは泳ぐ速度です。従って、f(b, y)-f(a, y) = (sqrt( (y-b)**2+w**2) - sqrt( (y-a)**2+w**2) )/sです。この式をs倍して変形してsqrt( ( (y-a)+(a-b) )**2+w**2) - sqrt((y-a)**2+w**2)とし、y'=y-aの関数だと思います。ここで、a-b > 0を用いると、この関数がy'について単調増加であることがわかります。これは(※)の式が成立している事を示します。