$\newcommand{\dp}{\text{dp}}$
鉄則本[1]を読んでてよくわからなくなったので備忘録として残しておきます。時間があったらLISの復元もやろうと思います。
問題設定
与えられた正整数列の最長増加部分列(LIS)の長さを求めてください。
ただし正整数列の長さは100000以下、各正整数の値は500000以下とします。
（出典：競技プログラミングの鉄則 演習問題集 A24 - LIS）
LISの長さを求める
前半の問題を解きます。
Part1. 愚直な実装
愚直に動的計画法を実装することを考えます。
$a[0],a[1],…,a[n-1]$を与えられた正整数列とし、$\dp[i]$を「$a[i]$を最終要素に持つ増加部分列の最大長さ」となるようにします。
$a[i]$を最終要素に持つような増加部分列は、次の二つの方法でしか作れません。
- 既存の増加部分列であって最終要素が$a[i]$より小さいものに$a[i]$をくっつける。
- $a[i]$のみからなる長さ1の増加部分列を作る。
従って、$\dp[0] = 1, \dp[i] = \max \lbrace \dp[j]+1 ~|~ a[j]<a[i], ~ j<i\rbrace$とすれば良いことが分かります。ただし$\max\varnothing = 1$です。
$\dp$テーブルを完成させた後は、$\max \lbrace \dp[i] \rbrace_{i=0}^{n-1}$を求めればLISの長さが計算できます。
ところがこのアルゴリズムでは計算量が$O(n^2)$となり、制約$n\le100000$の下では遅すぎます。
そこで、各$\dp[i]$の計算を高速化する方法を考えます。
Part2. 改良するには？
Part1では各$i$に対し、すべての$a[j]<a[i]$を満たす$j<i$について$\dp[j]$を調べ、どの増加部分列にくっつけるのが良いかを考えていました。
しかし、とある配列を考えればこの作業をもっと効率良く行うことができます。その配列を天下り的に導入すると理解が難しくなるので、まずこの問題への素直なアプローチを考えてみます。
最終要素が$a[i]$より小さい増加部分列を良い部分列と呼ぶことにします。$a[i]$をどの良い部分列にくっつけるのが良いでしょうか？勿論、「最長の良い部分列」にくっつけるのが最適です。なので、「番号$0$から番号$i-1$までの範囲で、増加部分列をすべて覚えておく」「そして、その増加部分列の長さと“それが良い部分列になるかどうか”が判断できるような何かを記録しておく」という発想に行き着きます。各増加部分列が良い部分列であるかどうかを判定していき、見つかった良い部分列の中で最長のものを選び出せば、$\dp[i]$が求まるというわけです。
では、番号$0$から番号$i-1$までの範囲の増加部分列をすべて覚えておく必要があるでしょうか？答えはNoです。その増加部分列の中には、“上位互換”“下位互換”が明確に存在しています。
「番号$0$から番号$i-1$までの範囲の増加部分列であって、長さが$x$のもの」を考えます。$x<a[i]$なら、$a[i]$をこれにくっつけで増加部分列が作れます。ここでそのような増加部分列は、最終要素が最小のものしか覚えておかなくて良いはずです。最終要素が小さければ小さいほどくっつけられる要素の幅が広がるからです。
これで何を覚えておくべきかが明確になりました。我々は正整数列を左側から見ていくわけですが、各$i$時点で「長さが$x$の増加部分列の最終要素として最小のもの」$(x \in \mathbb{N})$ さえ知っていれば良いわけです。
この発想を整理して、LISの長さを求めます。
Part3. 高速な解法
正整数列を左から見ていき、$\dp[i]$を求めようとしている段階を考えます。$L[x]$を、「（番号$i-1$までの範囲で）長さが$x$であるような増加部分列の最終要素としてあり得る値の最小値」となるように定めます。
$L[x]$は、定義により広義単調増加であるはずです。$a[i]$をくっつけられる増加部分列のうち最長のものの長さは「$L[x]<a[i]$であるような$x$の最大値」に他ならないので、この値は二分探索で見つけることができます。その値に$+1$したものが$\dp[i]$の値になります。
$L$の更新ですが、実は$L[\dp[i]] = a[i]$とすれば十分です。
証明
$0\le x < \dp[i]$である$x$に対して、$L[x]$は更新されません。実際、$\dp[i]$の取り方より$0\le x < \dp[i]$なら$L[x] < a[i]$が成り立ちます。$L$はその性質上、大きい値へ更新されるといったことは起こらないので、$L[x]$は更新され得ません。一方で、$x > \dp[i]$である$x$に対して、$L[x]$は更新されません。実際、$\dp[i]$の取り方より$L[x-1] \ge a[i]$となるのでそもそも$a[i]$をくっつけて長さ$x$の増加部分列を作ることができません。 そのため、$L[\dp[i]] = \min (a[i], L[\dp[i]])$と更新されるべきですが実はこの$\min$も外せて$L[\dp[i]] = a[i]$とできます。実際、やはり$\dp[i]$の取り方より$L[\dp[i]] \ge a[i]$です。ソースコード（C++）
#include <iostream>
#include <vector>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> a(n);
for (int i=0; i<n; i++){
cin >> a[i];
}
vector<int> dp(n);
vector<int> L(n);
int ans = 1;
for (int i=0; i<n; i++) L[i] = 2e9;
dp[0] = 1; L[0] = 0; L[1] = a[0];
for (int i=1; i<n; i++){
dp[i] = lower_bound(L.begin(),L.end(),a[i]) - L.begin();
L[dp[i]] = a[i];
ans = max(dp[i],ans);
}
cout << ans << endl;
}
参考文献
[1]米田優峻（2022）『競技プログラミングの鉄則 アルゴリズム力と思考力を高める77の技術』