AOJ - DPL_1 D (最長増加部分列) を解いてみた
AOJ - DPL_1 Dは、最長増加部分列(Longest Increasing Subsequence)です
最長増加部分列 | 動的計画法 | Aizu Online Judge
これが解けると、AtCoderの以下の問題も解けます
D: トランプ挿入ソート - AtCoder Beginner Contest 006 | AtCoder
また、関連問題は以下のブログが詳しいです
アルゴリズム自体の解説はWikipediaやGeeksForGeekが良かったです
- Longest increasing subsequence - Wikipedia
- Longest increasing subsequence problem - Algorithms Tutorial
- Dynamic Programming | Set 3 (Longest Increasing Subsequence) - GeeksforGeeks
- Longest Increasing Subsequence Size (N log N) - GeeksforGeeks
最長増加部分列の基本
最長増加部分列(LIS)とは
問題設定
まずはWikipediaの記述から...
In the first 16 terms of the binary Van der Corput sequence
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
a longest increasing subsequence is
0, 2, 6, 9, 11, 15.
This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,
0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
are other increasing subsequences of equal length in the same input sequence.
van der Corput 列*1の最初の16個の数値
0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
において、最長増加部分列は
0, 2, 6, 9, 11, 15.
この部分列は長さ6である、ということは（当たり前だが）7要素の増加部分列を持たない。この例における最長増加部分列は一意ではない、例えば
0, 4, 6, 9, 11, 15 もしくは 0, 4, 6, 9, 13, 15
は入力された同一の列内で等しい長さを持つ他の増加部分列であると言える
アルゴリズム
線形探索版のプログラム - O(N^2)
- 与えられる配列を arr[n]、最長増加部分列をlis[n] であるとする
- arr と lis の出来上がりは以下のようになる
- 上がarrayで下がlis
lisの配列にはそのインデックスまでの配列における増加部分列の長さが入る
| 9 | 5 | 2 | 8 | 7 | 3 | 1 | 6 | 4 | 5 |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 1 | 2 | 2 | 2 | 1 | 3 | 3 | 4 |
lis配列の最後に入る 4 が最長増加部分列となる。
サンプルプログラム
線形探索版のプログラム - O(N^2)
lines = <<'EOS' 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 EOS #lines = $stdin.read array = lines.split("\n") def get_lis(arr) lis_arr = Array.new(arr.length){1} length = 1 puts arr.to_s puts lis_arr.to_s for i in 1...arr.length for j in 0...i lis_arr[i] = lis_arr[j] + 1 if arr[j] < arr[i] and lis_arr[i] < (lis_arr[j]+1) end end puts lis_arr.to_s lis_arr.max end puts get_lis(array[0].split(" ").map(&:to_i).to_a)
- 探索対象の配列を i 回ループし、その中で j 回ループするので、計算量が O(n^2) になる、遅い
- これも動的計画法の１つらしい
二分探索版のプログラム - O(N log N)
lines = <<'EOS' 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15 EOS #lines = $stdin.read array = lines.split("\n") def ceil_index(array, l, r, key) while r-l > 1 m = l + (r-l)/2 if array[m] >= key r = m else l = m end end r end def get_lis(arr) tail = Array.new(arr.length) len = 1 tail[0] = arr.first for i in 1...arr.length if arr[i] < tail[0] tail[0] = arr[i] elsif arr[i] > tail[len-1] # v[i] extends largest subsequence tail[len] = arr[i] len = len + 1 else # option(a): use binary search # but, ruby's Array#bsearch_index requires # all array's elements sorted #idx = tail[0..i].compact.bsearch_index do |x| # x >= arr[i] #end # option(b): implement binary search yourself idx = ceil_index(tail, -1, len-1, arr[i]) tail[idx] = arr[i] end end len end puts get_lis(array[0].split(" ").map(&:to_i).to_a)
