UVa 12407 Speed Zones

問題

n個の層があり、i番目の層は、
y座標y = i * 100からy = (i + 1) * 100の、x軸方向に無限に伸びる帯になっている。

i番目の層を進む速度は、方向にかかわらずs[i]である。
いま、(0, 0)を出発して、(D, n * 100)の地点に到達したい。

最短でどれだけの時間がかかるか、求めよ。

制約条件

n≦100
0≦D≦10000
テストケースは50個以下。

方針

ラグランジュの未定乗数法による。

i番目の層における、x軸方向の移動量をxiと置く。
すると、目的関数fは、移動にかかる時間の合計なので、
f = √(1 + xi^2) / si

ここに、制約条件D = Σxiがかかる。
よってg = Σxi - D

f - λgと置くと、ラグランジュの未定乗数法より、fを最小にするxについて、
∂(f - λg) / ∂xi = 0が成り立つ。

これをλについて解くと、
D = Σλs[i] / √(1 - λ^2s[i]^2)という式が出てくる。

右辺はλについての増加関数であるので、
等号を成り立たせるλは二分探索で見つけられる。

ここから、xiが求まるため、かかる時間が求まる。

ソースコード

int n;
double s[100], d, x[100];
 
int main(){
    int CS;
    cin >> CS;
    rep(cs, CS){
     
        cin >> n >> d;
        rep(i, n) cin >> s[i], s[i] /= 100;
        d /= 100;
         
        double lo = 0, hi = INF, mid;
        rep(i, n) hi = min(hi, 1 / s[i]);
        lo = -hi;
         
        rep(i, 100){
            mid = (lo + hi) / 2;
            double sum = 0;
            rep(j, n) sum += mid * s[j] / sqrt(1 - mid * mid * s[j] * s[j]);
            if(sum > d) hi = mid;
            else lo = mid;
        }
         
        double ans = 0;
        rep(i, n){
            x[i] = mid * s[i] / sqrt(1 - mid * mid * s[i] * s[i]);
            ans += sqrt(1 + x[i] * x[i]) / s[i];
        }
        printf("Case %d: %.9f\n", cs + 1, ans);
    }
    return 0;
}