AtCoder ABC #134 E - Sequence Decomposing

E - Sequence Decomposing

問題

数列 が与えられたとき、数列を単調増加となるような部分数列に分けた場合に最小のグループ数を答える問題。

解説

公式解説には「広義の単調減少列の最大の長さ」を求めれば良いとあるが、ここがあまりしっくり来ていない。

が、とりあえず上記に従って解いてみる。

fn solve(aa: Vec<isize>) -> usize {
    let n = aa.len();
    let mut dp = vec![std::isize::MAX; n];

    for a in aa {
        let a = -a;
        let p = dp.upper_bound(&a);
        if a < dp[p] {
            dp[p] = a;
        }
    }

    dp.lower_bound(&std::isize::MAX)
}

upper_bound(), lower_bound()は自前のスニペット(TODO: 解説)だが、C++と似た仕様である。

「広義の単調減少列の長さ」を求めるアルゴリズムは「LIS(Longest Increasing Subsequence)」で検索すると見つかる。

dp[i]を「i+1の長さを持つ数列の内、最後の項がもっとも小さいもの」と置いている。今回は単調増加ではなく、単調減少列を見つけるため、項を負の数にして(let a = -a;)単調増加に変換していることに注意。

また「広義の単調増加」を見つけるため、lower_bound()ではなくupper_bound()を使用している点も注意。

最大の長さはdp[i]の定義からlower_bound()で簡単に見つけることができる。