なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

AOJ - DPL_1 D (最長増加部分列) を解いてみた

AOJ - DPL_1 Dは、最長増加部分列(Longest Increasing Subsequence)です

最長増加部分列 | 動的計画法 | Aizu Online Judge

これが解けると、AtCoderの以下の問題も解けます

D: トランプ挿入ソート - AtCoder Beginner Contest 006 | AtCoder

また、関連問題は以下のブログが詳しいです

hamayanhamayan.hatenablog.jp

アルゴリズム自体の解説はWikipediaやGeeksForGeekが良かったです

最長増加部分列の基本

最長増加部分列(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] であるとする
  • arrlis の出来上がりは以下のようになる
    • 上が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 log N)

  • 与えられる配列を arr[n]、最長増加部分列をtail[n] であるとする
  • arrtail の出来上がりは以下のようになる
    • 上がarrayで下がtail
    • Rubyなのでnilが入っているが、0でもよいだろう

tail配列には増加部分列の最後の要素をどんどん入れていく

9 5 2 8 7 3 1 6 4 5
1 3 4 5 nil nil nil nil nil nil

こちらのほうが早く、tailに実際の最長増加部分列が入るため *2、より良いアルゴリズムと言えそうだ。

サンプルプログラム

線形探索版のプログラム - 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) になる、遅い
  • これも動的計画法の1つらしい

二分探索版のプログラム - 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)
  • 探索対象の配列を i 回ループするのは同じだが、その中で二分探索するので、計算量が O(N log N)*3 になる、これは結構早い
  • Rubyの場合、Array#bsearch_index が探索に使えると思ったのだが、なぜかエラーが出るので結局自力実装を真似ている

*1:特に問題には関係ない、ただの数列と思って問題ない

*2:入らない、残念

*3:計算量がN * log Nになるということですぞ