LIS のリンク集
LIS(最長増加部分列)について、参考になる記事や資料をまとめました。
LIS(Longest Increasing Subsequence)は、数列の部分列のうち増加しているもので最長のもの、またはその長さです。素直な DP は ですが、「長さ の増加部分列の末尾として考えられる最小の値」を配列で持ち、各要素の置き場所を二分探索で求めると になります。また、「 で終わる増加部分列の最長の長さ」を値の座標についてのセグメント木や BIT で区間最大値として求める方法も で、重みつきの LIS や個数の数え上げに拡張しやすいです。
二分探索の方法では、狭義の増加(同じ値を許さない)なら lower_bound(Python では bisect_left)、広義の増加(同じ値を許す)なら upper_bound(bisect_right)を使います。資料によって「増加」がどちらを指すかが違うので注意してください。また、二分探索の方法で最後に残る配列は LIS そのものではありません。LIS を復元するには、各要素について直前の要素や、その要素で終わる LIS の長さを記録しておく必要があります。
まず読むもの
Section titled “まず読むもの”- LIS でも大活躍! DP の配列使いまわしテクニックを特集(けんちょん、Qiita)
- ナップサック DP の配列の使いまわしから始めて、LIS の二分探索による方法とセグメント木による方法を、どちらも「DP の配列を使いまわしたもの」として説明しています。重みつきの LIS である EDPC Q - Flowers も扱っています。C++ です。
- コードは
lower_boundを使う狭義の LIS で、広義の場合の書き換えや復元には触れていません。
- 最長増加部分列・最長共通部分列(いかたこのたこつぼ)
- 二分探索による方法、復元、セグメント木による方法、増加部分列への最小の分解(Dilworth の定理)を、表で具体例を追いながら説明しています。狭義なら
bisect_left、広義ならbisect_rightを使うこと、セグメント木による方法で同じ値をどの順に処理するかも書かれています。後半は最長共通部分列(LCS)です。 - 二分探索の Python のコードは、関数名(
longest_increasing_subsequence)と呼び出し(lis(...))が食い違っているので、そのままでは動きません。また、コメントの「a以下の値が初めて出てくるindex」は「a以上」の誤りです。
- 二分探索による方法、復元、セグメント木による方法、増加部分列への最小の分解(Dilworth の定理)を、表で具体例を追いながら説明しています。狭義なら
二分探索による方法と復元
Section titled “二分探索による方法と復元”- LIS - 最長増加部分列(yamate11のブログ)
- 長さだけを求める方法と、各要素の直前の要素の添字を記録して LIS を 1 つ復元する方法を、手順として短くまとめています。狭義なら
lower_bound、広義ならupper_boundと明記されています。C++ です。 - 添字の書き方に 0 始まりと 1 始まりが混ざっています。復元の最後の手順の「 なら」は「 なら」と読んでください(先頭の要素 も直前の項になりえます)。
- 長さだけを求める方法と、各要素の直前の要素の添字を記録して LIS を 1 つ復元する方法を、手順として短くまとめています。狭義なら
- ABC354 F - Useless for LIS の公式解説(AtCoder)
- 各要素で終わる LIS の長さと始まる LIS の長さを、値についてのセグメント木で求め、「両者の和から を引いたものが LIS の長さに等しいか」で、その要素が LIS に含まれうるかを判定しています。セグメント木による方法の使い方の例として読めます。
応用(2 次元 LIS、Dilworth の定理)
Section titled “応用(2 次元 LIS、Dilworth の定理)”2 つの値の両方が大きくなる列(箱の入れ子など)は、一方でソートしてからもう一方の LIS を求めることで解けます。このとき、1 つ目の値が同じものどうしがつながらないように、同じ値の中では 2 つ目の値の降順に並べるのが定番です。また、Dilworth の定理から、数列を狭義増加部分列に分けるときの最小の個数は、最長の広義減少部分列の長さに等しくなります。
- ABC038 D - プレゼント のユーザ解説(seekworser、AtCoder)
- 箱を の昇順、同じ では の降順に並べ、 の LIS を求める、という 2 次元 LIS の定番の解き方を短く説明しています。
- 競技プログラミングにおける最長部分増加列問題まとめ(はまやんはまやんはまやん)
- LIS を使う問題を、入れ子構造に帰着するもの、広義の LIS を使うもの、3 次元のものなどに分けて並べた問題集です。解説は各問題への短いコメントだけです。
- 2017 年の記事なので、AtCoder の問題へのリンクは古い形式の URL ですが、今の URL に転送されます。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”LIS を扱う講座はまだありません。
Python
Section titled “Python”- bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
bisect_leftは等しい要素の左側、bisect_rightは右側の位置を返します。狭義の LIS ならbisect_left、広義の LIS ならbisect_rightです。key引数は Python 3.10 で追加されました。LIS そのものには触れていません。
- 最長増加部分列(LIS)(Competitive programming notebook)
bisect_leftを使う長さの計算と、各要素で終わる LIS の長さを記録して後ろから復元する方法を、Python の短いコードで示しています。- 番兵の既定値が
INF=10**9なので、 を含む入力では長さを正しく数えられません。INF をもっと大きくしてください。
- Longest Increasing Subsequence(最長増加部分列)(Luzhiled’s Library)
- C++ の実装で、引数
strictで狭義(lower_bound)と広義(upper_bound)を切り替えられます。返すのは長さだけです。
- C++ の実装で、引数
- dp/longest-increasing-sequence.hpp(Nyaan’s Library)
- 狭義の LIS を 1 つ、添字の列で返す C++ の実装です。ファイル名は subsequence ではなく sequence です。ドキュメントはほとんどありません。
百科事典・英語の資料
Section titled “百科事典・英語の資料”- Longest increasing subsequence(英語版 Wikipedia)
- のアルゴリズムを、復元つきの擬似コードと具体例で説明しています。ほかに、LCS への帰着、Erdős–Szekeres の定理、ランダムな順列の LIS の長さが約 になることなども載っています。日本語版の記事はありません。
- 擬似コードは狭義の LIS ですが、本文では狭義か広義かを明記していません。
- Longest increasing subsequence(cp-algorithms)
- の DP、二分探索による の方法、セグメント木などのデータ構造による方法を、それぞれ復元の方法とあわせて説明しています(データ構造による方法の復元は省略)。広義の LIS、LIS の個数、増加しない部分列への最小の分解なども扱い、練習問題の一覧があります。
- 広義の場合は「二分探索を少し変える」とだけ書かれています。
upper_boundに変えればよいです。
- Longest Increasing Subsequence(USACO Guide)
- と の方法、セグメント木による方法を説明し、交差しない線分の最大個数や増加部分列への最小の分解(Dilworth の定理)などの応用と問題の一覧があります。コードは Python で、狭義の LIS です。
- Patience sorting(英語版 Wikipedia)
- カードを山に積んでいくソートで、山の数が LIS の長さに等しくなります。二分探索による方法と同じ考え方で、山の間にポインタを張って LIS を復元する方法も書かれています。
- 本文では「新しいカード以上の山に置く」、擬似コードでは「新しいカードより大きい山に置く」となっていて、狭義と広義が食い違っています。
- Dilworth’s theorem(英語版 Wikipedia)
- 半順序集合の最小の鎖分解の個数が最大の反鎖の大きさに等しいという定理と、その双対(Mirsky の定理)を証明つきで説明しています。LIS との関係は、Erdős–Szekeres の定理がこの定理の応用とみなせる、と一言触れているだけです。
- Library Checker - Longest Increasing Subsequence:狭義の LIS を 1 つ、添字の列で出力します。復元の verify 用です。
- CSES - Increasing Subsequence:狭義の LIS の長さを求める基本問題です。
- ABC006 D - トランプ挿入ソート:動かさないカードが増加部分列になることに気づくと、 から LIS の長さを引いたものが答えです。
- 競プロ典型 90 問 060 - Chimera(★5):左からの LIS と右からの LIS を各位置で組み合わせて、増加してから減少する最長の部分列を求めます。
- ABC038 D - プレゼント:縦・横ともに大きい箱にしか入れられない入れ子の段数を求める、2 次元 LIS の問題です。
- ARC126 B - Cross-free Matching:共有点のない線分を最大個数選びます。片方の端点でソートすると、もう片方の LIS になります。
- ABC134 E - Sequence Decomposing:数列を狭義増加部分列に分けるときの最小の個数を求めます。Dilworth の定理から、最長の広義減少部分列の長さです。
- EDPC Q - Flowers:重みつきの LIS で、セグメント木や BIT で区間最大値を求めます。
- ABC165 F - LIS on Tree:木の上の根からのパスごとの LIS を、DFS で二分探索の配列の変更を戻しながら求めます。
- ABC354 F - Useless for LIS:各要素が LIS に含まれうるかを判定します。各要素で終わる LIS と始まる LIS の長さを使います。
- ABC360 G - Suitable Edit for LIS:1 つの要素を好きな整数に置き換えたときの LIS の長さの最大値を求めます。
- ABC237 F - |LIS| = 3:LIS の長さがちょうど の数列を数えます。 と小さいので、二分探索の方法で持つ配列そのものを DP の状態にできます。
このブログの記事
Section titled “このブログの記事”- DOJ Beginner Contest 11 F - Laboratory
- 微生物を成長係数の順に並べたとき、 日目に選べる最大の種類数が、(個体数, 番号) の組の狭義の LIS の長さになることを使い、日数を二分探索しています。