Rustコトハジメ

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

LISを題材にした問題

配列内の数の関係性について議論している問題はよく出されていて、LIS (Longest Increasing Sequenceの略) が題材となってるものはLISだと気づかないことが多すぎる。

この記事では、LISについて復習して、LISを題材とした問題例をいくつか挙げることにする。

LISとは

配列が与えられた時、その中で単調増加している要素の最大長。例えば、1,3,2,4,3,5という配列が与えられた時、長さ4。

LISの考え方

上の例では、LISは4種類あるが、1,2,3,5を求める方法がある。

考え方は、左から舐めていって、常に数が小さい列を作っていく。例えば、上の例でいうと、

  1. []
  2. [1]
  3. [1,3]
  4. [1,2] // 2 < 3
  5. [1,2,4]
  6. [1,2,3] // 3 < 4
  7. [1,2,3,5]

とすれば良い。なぜ小さい場合に入れ替えるかというと、前の数が小さい方が、長い列が作れる可能性が単純に高まるからである。

これは、その都度二分探索をして挿入位置を決めていけばよい。したがって、一回あたりO(logN)でN回だから、トータルではO(NlogN)となる。

fn lis<T: Ord + Clone>(xs: &[T], inf: T) -> Vec<T> {
    let n = xs.len();
    let mut dp = vec![inf; n];
    for x in xs {
        let i = dp.lower_bound(&x);
        dp[i] = min(dp[i].clone(), x.clone());
    }
    return dp;
}

問題集

プレゼント

D - プレゼント

(w,h)の列が与えられる。この中から、wについてもhについても単調増加な列の最大長はいくつか?

方針は、wについて昇順、hについて降順でソートする。こうしたあと、hについてLISを計算すれば良い。どちらかについて単調増加を確定させるというのがポイント。hについて降順ソートするのは、同じwについて2個とれないから。