目次

最長増加部分列・最長共通部分列

競技プログラミングでは、「最長増加部分列(LIS)」や「最長共通部分列(LCS)」を求めるものが出題されることがある。
これらは動的計画法により高速に求めることができる。

用語の意味

部分列

ある数列や文字列 A=(a1,a2,...,aN)A=(a1,a2,...,aN) がある時、部分列(Subsequence)とは、AA からいくつかの要素を抽出した列。
飛び飛びでもよいが、順番は元から変わってはいけない。

別の言い方をすると、以下の手順で構築できる列 CC が部分列である。

空の列 ()() を部分列に含むかどうかは定義による。

最長増加部分列

AA の部分列のうち単調増加なものを AA の「増加部分列」という。

同じ値を許すかは定義によるが、ここでは許さない(狭義単調増加)とする。

増加部分列のうち、長さが最も長いものを AA の「最長増加部分列」(Longest Increase Subsequence, LIS)という。

LISの具体的な要素は複数通り考えられる場合もあるが、長さは AA により一意に決まる。

元の数列(5,3,7,4,1,4,6)(5,3,7,4,1,4,6)
増加部分列の例(5,7),(3,6),(3,4,6)(5,7),(3,6),(3,4,6)
最長増加部分列の例(3,4,6),(1,4,6)(3,4,6),(1,4,6)
最長共通部分列

2つの列 AABB に共通する部分列を、AABB の「共通部分列」という。

そのうち長さが最長のものを「最長共通部分列」(Longest Common Subsequence, LCS)という。

LCSの具体的な要素は複数通り考えられる場合もあるが、長さは一意に決まる。

最長増加部分列

最長増加部分列の長さ

動的計画法で求める。このアルゴリズムでは、最長増加部分列の内容自体は求まらない。

大きく分けて、二分探索を用いる方法と、セグメント木を用いる方法がある。前者の方が実装は楽。

二分探索を用いる方法

以下のDPをまず考える。

ある増加部分列の末尾に新たな要素 xx を追加できるかどうかは、現在の末尾要素が xx 未満かどうかさえ分かれば判定できる。
長さが同じなら末尾要素が小さい方が、追加できる xx の範囲が広いので、長さ毎に末尾が最も小さいものだけ記録しておけば十分となる。

以下の具体的なアルゴリズムでも示されるが、このDPは i1i1ii では更新箇所が1箇所しかない。
よって、DPを2次元配列で持つのではなく、ii の次元は省略し、jj を添字に持つ1次元配列を破壊的に更新していくことで、より高速に求められる。

  1. L=[]L=[] を用意する。
  2. i=1,2,...,Ni=1,2,...,N の順に以下を1つずつ処理する。現在処理中の要素を aiai とする。
    1. L<ai の場合、L の末尾に ai を追加する。
    2. それ以外の場合、L 上で二分探索して ai 以上の値が初めて出てくるindex k を求め、L[k]ai で置き換える。
  3. 最後まで処理した後、L の最大のindexが、最長増加部分列の長さとなる。

計算量 O(NlogN) で求めることができる。

狭義単調増加の場合はbisect_left(ai 以上が初めて出てくるindex)だが、広義単調増加の場合はbisect_right(ai を超える値が初めて出てくるindex)を用いる。

A = (3, 4, 8, 5, 1, 6, 2, 7)

i  Ai   L
        [-∞]
1   3   [-∞, 3]
2   4   [-∞, 3, 4]
3   8   [-∞, 3, 4, 8]
4   5   [-∞, 3, 4, 5]
5   1   [-∞, 1, 4, 5]
6   6   [-∞, 1, 4, 5, 6]
7   2   [-∞, 1, 2, 5, 6]
8   2   [-∞, 1, 2, 5, 6, 7]    →  LIS長は 5

Lを で初期化した長さ N の配列として初期化する流儀もある。
末尾に加えるか更新するかの場合分けが不要となりコードは短くなるが、代わりに毎回二分探索をおこなう必要がある。

Python実装例

セグメント木(or BIT)を用いる方法

二分探索を用いる方法は、実装がシンプルではあるが、拡張性の面ではやや低い。
最長増加部分列を求めるのにはセグメント木を使う方法もあり、そちらは多少、ひねったバリエーション問題にも対応できる。

以下のDPを定義する。

DP[i]=0i=1,...,N)で初期化した上で、このDP配列をセグメント木に載せる。

i ではなく、ai が小さい順に処理する。同率の場合は、indexが後の方から処理する。
(※広義単調増加の場合は、前の方から処理する)

ai について処理する際、DP 配列の「[1,i) の区間における最大値 + 1」が、DP[i] となる。
区間最大値はセグメント木やBITで取得できるので、これで DP[i] を計算し、更新する。

最終的に、DP 全体の中での最大値が答えとなる。

こちらも計算量のオーダーは O(NlogN) となる。
二分探索と比べて定数倍や必要なメモリは重くなるが、一般的な競技プログラミングの制約の前ではまぁ、だいたい気にしなくていい。

i    1  2  3  4  5  6  7  8
A = (3, 4, 7, 5, 1, 5, 7, 3)

i  Ai   DP
        [0, 0, 0, 0, 0, 0, 0, 0]
5   1   [0, 0, 0, 0, 1, 0, 0, 0]  [1, i)の最大値(波線区間) + 1 で、DP[i] を更新
         ~~~~~~~~~~
8   3   [0, 0, 0, 0, 1, 0, 0, 2]
1   3   [1, 0, 0, 0, 1, 0, 0, 2]
2   4   [1, 2, 0, 0, 1, 0, 0, 2]
6   5   [1, 2, 0, 0, 1, 3, 0, 2]
4   5   [1, 2, 0, 3, 1, 3, 0, 2]
7   7   [1, 2, 0, 3, 1, 3, 4, 2]
3   7   [1, 2, 3, 3, 1, 3, 4, 2]    → LIS長は4

最長増加部分列の復元

具体的な最長増加部分列の1つを求める場合。

二分探索を用いる方法で、L の他に、以下の情報も持ってDPする。

最後までDPしたら、復元する。

prevの記録・LISの復元は O(N) でできるので、計算量は変わらず O(NlogN) となる。

バリエーション

最長増加部分列の個数

条件として、「部分列として同じであっても取り出した位置が異なる場合は別カウント」とする。

セグメント木を使う方法を拡張する。

セグメント木なら、これは適切にマージできる。(長さが同じなら個数を合算し、どちらかが大きいならそちらを継承する)

ai について処理する際、[0,i) の区間を求め、(最長の長さ+1, 個数) が DP[i] となる。

計算量のオーダーは O(NlogN) となる。

最長共通部分列

2つの文字列 S,T がある時、「S の部分列でもあり、T の部分列でもある」文字列を共通文字列という。

そのうち最長のものを最長共通部分列(Longest Common Subsequence)という。

Sabcbdabc
Tbdcaba
LCSbcba,bdabなど

最長共通部分列の長さ

文字列 S,T が与えられたとき、2つの最長共通部分列の長さを求めましょう、という問題。

以下のDPを考える。

DP[i,j] を求めるには、

DP[i,j] を埋めるには、DP[i1,j1],DP[i1,j],DP[i,j1] が埋まっている必要がある。
DP[0,]DP[,0]0 確定なので埋めておき、 あとは 'for i in (1,…,|S|) for j in (1,…,|T|)' の2重ループで処理すればよい。

DP[|S|,|T|] が最長共通部分列の長さとなる。
計算量は O(|S||T|)

S = XMJYAUZ
T = MZJAWXU

      0 1 2 3 4 5 6 7
        M Z J A W X U
0   | 0 0 0 0 0 0 0 0
1 X | 0 0 0 0 0 0 1 1
2 M | 0 1 1 1 1 1 1 1
3 J | 0 1 1 2 2 2 2 2
4 Y | 0 1 1 2 2 2 2 2
5 A | 0 1 1 2 3 3 3 3
6 U | 0 1 1 2 3 3 3 4
7 Z | 0 1 2 2 3 3 3 4

DPの持たせ方を変えた別解法

最長共通部分列の復元

長さを求める際のDPの結果から、具体的な最長共通部分列の1例を復元できる。

DPテーブルから逆向きに復元する。(i,j)=(|S|,|T|) で初期化する。
また、復元結果を記録する配列 U を空で初期化する。

DP[i,j]=DP[i,j1] または DP[i,j]=DP[i1,j] の時

同じである数字の方に (i,j) を移動する。両方同じ場合は適当に1つ選んで移動する。

それ以外の時

Si=Tj となっている。U にその文字を加え、(i1,j1) に移動する。

DP[i,j]=0 になったら終了。
U をひっくり返すと、最長共通部分列となる。

      0 1 2 3 4 5 6 7
        M Z J A W X U
0   | 0 0 0 0 0 0 0 0
1 X |⓪ 0 0 0 0 0 1 1
2 M | 0❶① 1 1 1 1 1
3 J | 0 1 1❷ 2 2 2 2
4 Y | 0 1 1② 2 2 2 2
5 A | 0 1 1 2❸③③ 3
6 U | 0 1 1 2 3 3 3❹  丸付きの数字を辿っていき、
7 Z | 0 1 2 2 3 3 3④  黒丸の数字を拾っていくと、LCS(の1つ)は MJAU と復元できる

バリエーション

一方に出てくる文字に重複がない場合

S,T いずれか一方に出てくる文字が全て異なることが分かっていれば、より少ない計算量で求められる。
ここでは S の文字が全て異なるとする。

S に出てくる順に、文字を数値に置き換える。T もその置換に従って置き換える。S に出てこない文字は取り除く。

S =  B R O W N C A T
      ↓
S'=  1 2 3 4 5 6 7 8

T =  W H I T E C O W
      ↓
T'=  4 x x 8 x 6 3 4    Sに出てこない文字(x)は、取り除く

最長共通部分列の長さは、T の最長増加部分列の長さとなり、O(|S|+|T|log|T|) で求められる。

最長共通部分列の個数

取り出し位置の個数

「共通部分列として同じであっても、S,T から取り出した位置が異なる場合は別カウント」の場合の個数を数える。

長さを求めるものとは別に、個数を数えるDP配列を用意する。

DPc[0,]=DPc[,0]=1、他は 0 で初期化する。

遷移では、以下のようにすればよい。DPc[i,j] を求める。(1i|S|,1j|T|)

4つめの更新で減算しているのは、DPc[i1,j1] で数えられている最長共通部分列が 「→↓」と「↓→」の2通りの経路で重複して DPc[i,j] に足し込まれるのを防ぐためである。

文字列としての個数

S,T から取り出した位置が異なっても、文字列として同じ場合は1カウント」の場合の個数を数える。

上記の4種類のDP遷移のうち、下3つを、Si=Tj である場合は行わないようにすればよい。つまり、

でよい(未検証)

お気持ち