【Python】増加部分と減少部分がそれぞれ異なる2つの配列からなる最長ビトニックシーケンスを求める方法

2つの配列が与えられたとき、次の条件を満たす最長のビトニックシーケンス(バイトニック配列)を求める問題を考えてみましょう。「増加する部分」は1つ目の配列の部分列であり、「減少する部分」は2つ目の配列の部分列である必要があります。

たとえば、入力が A = [2, 6, 3, 5, 4, 6]、B = [9, 7, 5, 8, 4, 3] である場合、出力は [2, 3, 4, 6, 9, 7, 5, 4, 3] となります。

解法のアプローチ

この問題は、最長増加部分列(LIS: Longest Increasing Subsequence)を求めるアルゴリズムを応用することで効率的に解けます。基本的なアイデアは以下のとおりです。

• 配列Aに対してLISを計算し、その結果をビトニックシーケンスの「増加部分」とします。
• 配列Bを逆順にしてからLISを計算すると、元のBにおける最長の「減少部分」が得られます。
• tails_idx 配列と二分探索を使うことで、O(n log n) の時間計算量でLISを求められます。
• prev_idx 配列に直前の要素のインデックスを記録しておき、後から実際のシーケンスを復元します。

アルゴリズムの手順

1. 二分探索関数 index_ceiling() を定義する

引数として arr、T、left、right、key を受け取ります。T は tails_idx 配列に相当し、key 以上の値となる最小の位置を二分探索で見つけて返します。

• right - left > 1 の間、次を繰り返します。
  • mid := left + (right - left) // 2
  • arr[T[mid]] >= key なら right := mid、そうでなければ left := mid
• 最後に right を返します。

2. 最長増加部分列を求める関数 long_inc_seq() を定義する

• n := A のサイズ
• tails_idx := サイズ n の配列(0で初期化)
• prev_idx := サイズ n の配列(-1で初期化)
• length := 1
• i を 1 から n-1 まで繰り返します。
  • A[i] < A[tails_idx[0]] の場合:tails_idx[0] := i
  • A[i] > A[tails_idx[length - 1]] の場合:prev_idx[i] := tails_idx[length - 1]、tails_idx[length] := i、length を 1 増やす
  • それ以外の場合:pos := index_ceiling(A, tails_idx, -1, length - 1, A[i]) を求め、prev_idx[i] := tails_idx[pos - 1]、tails_idx[pos] := i とする
• i := tails_idx[length - 1] とし、i >= 0 の間、answer の末尾に A[i] を追加しながら i := prev_idx[i] で要素を辿ります。

3. メイン処理

• n1 := A のサイズ、n2 := B のサイズ
• long_inc_seq(A) を呼び出す
• answer を反転させる
• B を反転させる
• long_inc_seq(B) を呼び出す
• answer を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

answer = []
def index_ceiling(arr,T, left,right, key):
    while (right - left > 1):
       mid = left + (right - left) // 2;
       if (arr[T[mid]] >= key):
          right = mid
       else:
          left = mid
    return right
def long_inc_seq(A):
    n = len(A)
    tails_idx = [0]*(n)
    prev_idx = [-1]*(n)
    length = 1
    for i in range(1, n):
       if (A[i] < A[tails_idx[0]]):
          tails_idx[0] = i
       elif (A[i] > A[tails_idx[length - 1]]):
          prev_idx[i] = tails_idx[length - 1]
          tails_idx[length] = i
          length += 1
       else:
          pos = index_ceiling(A, tails_idx, -1, length - 1, A[i])
          prev_idx[i] = tails_idx[pos - 1]
          tails_idx[pos] = i
    i = tails_idx[length - 1]
    while(i >= 0):
       answer.append(A[i])
       i = prev_idx[i]
def long_bitonic(A,B):
    n1 = len(A)
    n2 = len(B)
    global answer
    long_inc_seq(A)
    answer = answer[::-1]
    B = B[::-1]
    long_inc_seq(B)
A = [2, 6, 3, 5, 4, 6]
B = [9, 7, 5, 8, 4, 3]
long_bitonic(A,B)
print(answer)

入力

[2, 6, 3, 5, 4, 6], [9, 7, 5, 8, 4, 3]

出力

[2, 3, 4, 6, 9, 7, 5, 4, 3]

まとめ

このアルゴリズムでは、二分探索を用いたLIS計算によって、配列Aからの最長増加部分列と、反転した配列Bからの最長増加部分列(= 元のBにおける最長減少部分列)を組み合わせることで、目的のビトニックシーケンスを O(n log n) の計算量で効率的に求めることができます。