【解答】アルゴリズムイントロダクション：15.4 最長共通部分列

## 問題15.4-1

> ⟨1, 0, 0, 1, 0, 1, 0, 1⟩ と ⟨0, 1, 0, 1, 1, 0, 1, 1, 0⟩ の最長共通部分列（LCS）を１つ求めよ．

### 解答

* ⟨1, 0, 0, 1, 1, 0⟩
* または ⟨1, 0, 1, 0, 1, 0⟩ ([walkccc.me][1])

### 丁寧な説明

1. **動的計画法の行列構築**
   長さ m = 8 の X と長さ n = 9 の Y に対し，c\[i,j] を X の長さ i プレフィックスと Y の長さ j プレフィックスの LCS 長とすると，以下の再帰式で表せます：

   ```
   c[i,j] = 0                                   (i=0 または j=0)
   c[i,j] = c[i-1,j-1] + 1     if X[i] == Y[j]
   c[i,j] = max(c[i-1,j], c[i,j-1])  otherwise
   ```

   これを行列 c\[0..8,0..9] に対して行・列を順に埋めていけば，c\[8,9] = 6 が得られます．

2. **共通部分列の復元**
   c\[i,j] の値を見ながら，PRINT-LCS アルゴリズムで復元します．

   * X\[i] == Y\[j] の場合は両方を含めて対角に移動
   * そうでない場合は，c\[i-1,j] と c\[i,j-1] を比較し，大きいほうの方向へ移動

   これにより長さ6の部分列⟨1,0,0,1,1,0⟩（または別の等長解）を得られます．

3. **なぜこれが最長か**

   * 例えば最初の要素 X\[1]=1 を残すなら，Y の中で最初に現れる 1 の位置を j=2 とし，その後のサブ問題として X\[2..8], Y\[3..9] の LCS を求める．
   * 再帰的に同様の判断を行い，最適部分構造に基づいて最大長を得る．

---

## 問題15.4-2

> 完成済みの c テーブルと元の列 X = ⟨x₁,…,xₘ⟩，Y = ⟨y₁,…,yₙ⟩ を用い，b テーブルを使わずに O(m+n) 時間で LCS を復元する擬似コードを示せ．

### 解答

```plaintext
PRINT-LCS(c, X, Y, i, j)
    if c[i,j] == 0
        return
    if X[i] == Y[j]
        PRINT-LCS(c, X, Y, i-1, j-1)
        print X[i]
    else if c[i-1,j] > c[i,j-1]
        PRINT-LCS(c, X, Y, i-1, j)
    else
        PRINT-LCS(c, X, Y, i, j-1)
```

このアルゴリズムは再帰的に対角・上・左のいずれかに移動し，文字を出力する． ([walkccc.me][1])

### 丁寧な説明

1. **b テーブル不要の理由**
   通常，b\[i,j] は c の計算時に選択した経路（↖, ↑, ←）を記録しているが，c\[i,j] の値と隣接する c の値（c\[i-1,j-1], c\[i-1,j], c\[i,j-1]）を比較するだけで，どの遷移で計算したかをその場で判断できる．

2. **再帰フロー**

   * c\[i,j]=0 に到達するまで再帰
   * 対角（↖）の場合は LCS の末尾に X\[i]（=Y\[j]）を含める
   * 上（↑）か左（←）かを比較し，多い方へ進む

3. **計算量**

   * 一度訪問した (i,j) は必ず再帰で一度のみ出力ルーチンを通過
   * 再帰深さは高々 m+n，文字列出力を合わせて O(m+n) で完了する．

---

## 問題15.4-3

> O(mn) 時間で動作する LCS-LENGTH のメモ化（トップダウン）バージョンを示せ．

### 解答

```plaintext
MEMO-LCS-AUX(X, Y, i, j)
    if c[i,j] > -1
        return c[i,j]
    if i == 0 or j == 0
        return c[i,j] = 0
    if X[i] == Y[j]
        return c[i,j] = MEMO-LCS-AUX(X,Y,i-1,j-1) + 1
    return c[i,j] = max(
        MEMO-LCS-AUX(X,Y,i-1,j),
        MEMO-LCS-AUX(X,Y,i,j-1)
    )

MEMO-LCS-LENGTH(X, Y)
    let c[0..m,0..n] be new array, 初期値を -1 に設定
    return MEMO-LCS-AUX(X, Y, m, n)
```

  ([walkccc.me][1])

### 丁寧な説明

1. **メモ化による重複計算の排除**
   再帰的 LCS-LENGTH は同じ (i,j) を繰り返し計算しうるが，c\[i,j] に結果を一度だけ格納し，再利用することで各 (i,j) は最大1度しか計算されない．

2. **時間計算量**

   * 可能なサブ問題数は (m+1)(n+1)=Θ(mn)
   * 各再帰呼び出しは定数回のメモ化テーブル参照と定数時間比較
   * よって合計 Θ(mn) 時間

3. **空間計算量**

   * c テーブルに Θ(mn) 空間
   * 再帰深さは Θ(m+n) のオーバーヘッド

---

## 問題15.4-4

> 長さ m, n の列の LCS 長さを求める際，c テーブルを 2·min(m,n) エントリ＋O(1) 追加空間だけで計算する方法を示せ．さらに，min(m,n) エントリ＋O(1) 空間で同様を実現する方法も示せ．

### 解答

* **2·min(m,n) エントリを使う方法**
  各ステップで「現在行」と「１つ前の行」のみ保持し，それ以前の行は解放する．

* **min(m,n) エントリを使う方法**
  c\[i,j] の計算に必要なのは c\[i-1,j], c\[i,j-1], c\[i-1,j-1] の３つのみ．
  内部ループで，列方向（あるいは行方向）の１次元配列だけを走査し，必要なくなった要素を都度上書きすることで，Θ(min(m,n)) の配列だけで実現できる． ([walkccc.me][1])

* 以下、具体例 **X=⟨A,B,C⟩,Y=⟨A,C⟩** での配列遷移を、prev_row／curr_row の値でステップごとに示します。
```plaintext
// 初期状態
prev_row = [0, 0, 0]   // j = 0,1,2
curr_row = [0, 0, 0]

// i = 1 (X[1] = A) のループ開始
// ── j = 1
//    X[1]==Y[1] (A==A) なので
//    curr_row[1] = prev_row[0] + 1 = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    X[1]!=Y[2] (A!=C) なので
//    curr_row[2] = max(prev_row[2], curr_row[1]) = max(0,1) = 1
//    → curr_row = [0, 1, 1]

// i=1 終了後に swap
prev_row = [0, 1, 1]
curr_row = [0, 1, 1]    ←（次 i の前に通常はリセットして使う）

// i = 2 (X[2] = B) のループ開始
// curr_row を [0,0,0] にリセット
curr_row = [0, 0, 0]
// ── j = 1
//    B!=A → curr_row[1] = max(prev_row[1], curr_row[0]) = max(1,0) = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    B!=C → curr_row[2] = max(prev_row[2], curr_row[1]) = max(1,1) = 1
//    → curr_row = [0, 1, 1]

// i=2 終了後に swap
prev_row = [0, 1, 1]
curr_row = [0, 1, 1]

// i = 3 (X[3] = C) のループ開始
// curr_row を [0,0,0] にリセット
curr_row = [0, 0, 0]
// ── j = 1
//    C!=A → curr_row[1] = max(prev_row[1], curr_row[0]) = max(1,0) = 1
//    → curr_row = [0, 1, 0]
// ── j = 2
//    C==C → curr_row[2] = prev_row[1] + 1 = 2
//    → curr_row = [0, 1, 2]

// i=3 終了後に swap
prev_row = [0, 1, 2]
curr_row = [0, 1, 2]

// 最終的に LCS 長さ = curr_row[2] = 2
```

### 丁寧な説明

1. **行単位スライディングウィンドウ**

   * 通常，c テーブルは (m+1)×(n+1) だが，各 i 行を計算するときは i-2 行より前は二度と参照しない．
   * よって常に直前２行のみメモリ上に残し，i 行目を計算後に i-2 行を解放すれば，必要セル数は 2·(n+1)．

2. **１次元配列の in-place 更新**

   * 列を j=1…n と走査しながら 1 次元配列 C\[j] を更新
   * C\[j] ← max(prev\_C\[j], C\[j-1], prev\_C\[j-1]+1 など) の形で，必要な情報を一時変数 prev に持たせる
   * これにより min(m,n) の配列長さだけで計算可能

3. **計算量**

   * 各セルの更新は O(1)
   * 全セル数 mn に比例して計算：Θ(mn) 時間

---

## 問題15.4-5

> 長さ n の数列に対し，最長単調増加部分列（LIS）を O(n²) 時間で求めるアルゴリズムを示せ．

### 解答

最長単調増加部分列（LIS：Longest Increasing Subsequence）とは，次のように定義される問題です。

---

## 単調増加部分列とは？
### 定義

* 与えられた長さ $n$ の数列

  $$
    A = \langle a_1, a_2, \dots, a_n\rangle
  $$

* その「部分列」（subsequence）とは，元の数列からいくつかの要素を取り出して，元の順序を保ったまま得られる新しい列のこと。
  例えば，$\langle a_2, a_5, a_7\rangle$ や $\langle a_1, a_3, a_4, a_6\rangle$ など。

* 「単調増加」は各要素が前より大きい（厳密増加）ことを意味する：
  部分列 $\langle b_1, b_2, \dots, b_k\rangle$ が単調増加なら

  $$
    b_1 < b_2 < \dots < b_k
  $$

  を満たします。

* **最長単調増加部分列（LIS）** は，すべての単調増加部分列の中で最も長いものを指し，その長さを求めたり，実際の部分列を復元したりする問題です。

---

### 例

たとえば，

$$
  A = \langle 3,\, 1,\, 8,\, 2,\, 5,\, 6,\, 4,\, 7\rangle
$$

このときの単調増加部分列の例としては

* $\langle 3,\, 8\rangle$（長さ2）
* $\langle 1,\, 2,\, 5,\, 6,\, 7\rangle$（長さ5）
* $\langle 1,\, 5,\, 6,\, 7\rangle$（長さ4） などがあります

この中で最も長いものは長さ5の

$$
  \langle 1,\, 2,\, 5,\, 6,\, 7\rangle
$$

ですから，この列の LIS の長さは 5，LIS のひとつの具体例は上記の部分列になります。

---


1. 元の数列 L をコピーしてソートし，L′ を得る（昇順）
2. L と L′ の LCS を求める（DP を使えば Θ(n²)）
3. その共通部分列は単調増加かつ最長である ([walkccc.me][1])

```plaintext
PRINT-LCS(c, X, Y)
    n = c[X.length, Y.length]
    let s[1..n] be a new array
    i = X.length
    j = Y.length
    while i > 0 and j > 0
        if x[i] == y[j]
            s[n] = x[i]
            n = n - 1
            i = i - 1
            j = j - 1
        else if c[i - 1, j] ≥ c[i, j - 1]
            i = i - 1
        else j = j - 1
    for i = 1 to s.length
        print s[i]
```
```
MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    m = |X|
    n = |Y|
    if c[m, n] != 0 or m == 0 or n == 0
        return
    if x[m] == y[n]
        b[m, n] = ↖
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y[1..n - 1], c, b) + 1
    else if MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b) ≥ MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
        b[m, n] = ↑
        c[m, n] = MEMO-LCS-LENGTH-AUX(X[1..m - 1], Y, c, b)
    else
        b[m, n] = ←
        c[m, n] = MEMO-LCS-LENGTH-AUX(X, Y[1..n - 1], c, b)
```
```
MEMO-LCS-LENGTH(X, Y)
    let c[1..|X|, 1..|Y|] and b[1..|X|, 1..|Y|] be new tables
    MEMO-LCS-LENGTH-AUX(X, Y, c, b)
    return c and b
```

[walkccc.me][1]

### 丁寧な説明

* L′ は L の昇順ソートなので，L′ の任意の部分列は単調増加．
* LCS(L, L′) は両方に現れる最長の共通部分列，故 L′ の性質からその間で最長単調増加部分列を得る．
* ソートは O(n log n) だが，LCS 部分が Θ(n²) を支配するため全体は O(n²)．

---

## 問題15.4-6 ★

> 長さ n の数列に対し，最長単調増加部分列を O(n log n) 時間で求めるアルゴリズムを示せ（ヒント：長さ i の候補部分列の「末尾」を管理し，二分探索を用いる）．

### 解答

```plaintext
LONG-MONOTONIC(A[1..n])
    let B[1..n] ← +∞      // B[i] は長さ i の部分列の末尾の最小値
    let P[1..n] be new array  // 連結リストで復元用ポインタを保持
    L ← 0
    for i = 1 to n
        // 長さ 1..L の中で，B[j] < A[i] となる最大 j を二分探索
        j ← BinarySearchLargest( B[1..L], < A[i] )
        B[j+1] ← A[i]
        P[i] ← end index of 値 B[j] に対応する要素
        if j+1 > L
            L ← j+1
    // 復元：末尾が長さ L の要素から P ポインタでたどる
    return 再構築した部分列
```

* 各要素ごとに B の二分探索で O(log n)
* 全体で O(n log n) 時間 ([walkccc.me][1])

### 丁寧な説明

1. **配列 B の意味**
   B\[i] は「長さ i の増加部分列」のうち，末尾が取りうる最小値を保持する．
2. **二分探索の活用**
   A\[i] を読むごとに，B\[1..L] から A\[i] を挿入すべき位置 j+1 を二分探索で決定．
3. **部分列の復元**
   P ポインタで，A\[i] を B\[j+1] に更新したときの直前要素の位置を記録し，最後に長さ L の末尾要素から逆順にたどって出力．
4. **計算量**

   * 各 i で二分探索 O(log n)
   * 復元も O(n)
   * 合計 O(n log n)

---


[1]: https://walkccc.me/CLRS/Chap15/15.4/ "15.4 Longest common subsequence - CLRS Solutions"