AtCoder Beginner Contest 134：E - Sequence Decomposing

問題
解法
解答

問題

https://atcoder.jp/contests/abc134/tasks/abc134_e

解法

単調増加列の数を最小化すればよい．既に色を塗った整数以外で新しく単調増加列を構成することを考える．ここで，残っている数字の中で最も大きいもののうち一番左にあるものは新たに作る単調増加列の終端になる．なぜならば，この数字より大きいものはないから．次に，この数字より前の位置にある中で最も大きいもののうち一番左にあるものを先ほどの数字の前にする．これを繰り返すことで単調増加列を 1 つ構成出来る．数字を追加する各段階で最も大きい数字を選んでいるので，単調増加列の数を最小化することができる．O(N * 3logN) ぐらい？