Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Educational DP-Z Frog 3】Convex Hull Trickの勉強

はいはいグラフとみて最短路乙と思いきや、無理やんけと気づいて絶望した。

Z - Frog 3

問題

長さNの単調増加するhiが与えられる。かえるがi番目にいるとき、j=i+1,...,Nに飛ぶことが出来て、コスト(hj-hi)2+Cを払う。かえるは最初i=1にいる。i=Nに到達する最小コストを求めよ。

方針

全ノードに経路を張って最短路という方針でまず考える。単純にやると辺を追加する段階でMLEすることがわかる。では、MLEせずに何か省略して出来るだろうかと考えたが無理だった。hiが単調増加してることを利用すれば計算量削減出来そうな感じもするのだが、ギブアップ。

想定は、Convex Hull Trickという問題に帰着させるもの。Convex Hull Trickというのは、たくさん数直線があった時に、あるxのところで一番上(または下)にある数直線のy座標を求めるというもの。イメージでいうとこんな感じ。

f:id:akiradeveloper529:20190927124414j:plain

この限定された問題を解く解法は、数直線の追加O(logN)、クエリO(logN)のアルゴリズムが存在する。詳しくはこちら。今回はこちらにあるアルゴリズムを実装した。

Convex-Hull Trick - sataniC++

というわけで、この問題をどうやってConvex Hull Trickに帰着させるかが問題になる。

dp[i] := iでの最小コスト

と定義すると、これは、

dp[i] = min { dp[j] + (h[i]-h[j])2 + C }

となる。これを分解すると、

dp[i] = min { -2h[j]h[i] + dp[j] + h[j]^2 } + h[i]^2 + C

を得る。このminの部分を求めたい。

この式は、i以前に、y=-2[hj]x + dp[j]+h[j]^2という数直線を描いていった時に、x=h[i]との交点のうちもっとも小さいものを求めよというConvex Hull Trickと見ることが出来る。

実装

fn solve() {
    input!{
        N:usize,C:i64,
        h:[i64;N]
    }
    // dp[i]
    // 0<=j<i
    // = min { dp[j] + (h[i]-h[j])^2 + C }
    // = min { dp[j] + -2h[j]h[i] + h[j]^2 + h[i]^2 + C}
    // = min { -2h[j]h[i] + dp[j] + h[j]^2 } + h[i]^2 + C

    let mut cht = ConvexHullTrick::new();
    let mut dp = vec![0;N];
    dp[0]=0;
    cht.add(-2*h[0], dp[0]+h[0]*h[0]);

    for i in 1..N {
        let minv=cht.get(h[i], |l:i64,r:i64| { l>=r });
        dp[i]=minv+h[i]*h[i]+C;
        cht.add(-2*h[i], dp[i]+h[i]*h[i]);
    }

    println!("{}",dp[N-1]);
}

ライブラリはこちらにあります。GitHub - akiradeveloper/rust-comp-snippets

考察

このシリーズは解説がなくて、分からない時に他人のACコードを読んで理解することを求められるけど、その中にたまたま丁寧にコメントをしているものがあって助かった。

Convex Hull Trickを利用した問題はわりと出るらしいので、ここで学べて僥倖。