Rustコトハジメ

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

LCSを使ってLISを実装する

LISのことを考えていたら、これは入力列をソートしたものとのLCSで計算出来るのではないかとふと思ったので実験します。

具体的には、LIS(A) = LCS(A, A.sorted.dedup)ですね。

直感的には正しいような気がします。というか意味合いとしては、A.sorted.dedupとのLCSをとるということは、最長の増加部分列を浮き出させることに当たりますから、定義通りとも言えます。

fn solve() {
    input! {
        N: usize,
        A: [usize; N],
    }

    let mut B = A.clone();
    B.sort();
    B.dedup();

    println!("{}", lcs(&A, &B));
}

をDPL_1_Dを使って実験してみます。

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_D

結果は、MLEしました。

基本的なテストは通ってるので、アルゴリズムとしては正しいのではないかと思いますが、2次元のDPテーブルをとっているのが原因だと思います。この問題ではNが10の5乗なので最悪でメモリが100GBくらいいきます。計算量もN2なのでやはりどのみち話にならず、この問題はNlogNのアルゴリズムを採用するしか通す方法はないと思いますが、今回は正しいかどうかを知りたかっただけなので、良かったことにします。