C++で増加部分と減少部分がそれぞれ異なる配列からなる最長ビットニック列を求める方法

ビットニック列とは

ビットニック列(バイトニック列)とは、最初に単調に増加し、その後に単調に減少する数列のことです。本記事では、2つの配列が与えられたときに、以下の条件を満たす最長のビットニック列をC++で求める方法を解説します。

• 増加部分は1つ目の配列から取られ、その配列の部分列であること
• 減少部分は2つ目の配列から取られ、その配列の部分列であること

入力例と出力例

例1

arr1[] = {2, 6, 3, 5, 4, 6},
arr2[] = {9, 7, 5, 8, 4, 3}

出力:

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

この例では、増加部分「2, 3, 4, 6」がarr1の部分列となり、減少部分「9, 7, 5, 4, 3」がarr2の部分列になっています。

例2

arr1[] = {3, 1, 2, 4, 5},
arr2[] = {6, 4, 3, 2}

出力:

1, 2, 4, 5, 6, 4, 3, 2

アルゴリズムの考え方

基本的な発想はシンプルで、以下の手順で結果を組み立てます。

1. 1つ目の配列から最長増加部分列(LIS)を求める
2. 2つ目の配列から最長減少部分列(LDS)を求める
3. 両者を連結してビットニック列を構成する

最長増加部分列は、二分探索を用いることでO(n log n)の計算量で効率的に求められます。2つ目の配列については、あらかじめ配列を反転してからLISを求めれば、結果的に最長減少部分列と同じものが得られるという仕組みです。

C++による実装例

// C++: 増加部分と減少部分が異なる配列からなる
// 最長ビットニック列を求めるプログラム
#include <bits/stdc++.h>
using namespace std;
vector<int> res1;

// 二分探索によるユーティリティ関数(ceil値の取得)
int GetCeilIndex(int arr[], vector<int>& T1, int l1,
int r1, int key1){
    while (r1 - l1 > 1) {
        int m1 = l1 + (r1 - l1) / 2;
        if (arr[T1[m1]] >= key1)
            r1 = m1;
        else
            l1 = m1;
    }
    return r1;
}

// LIS(最長増加部分列)を求める関数
void LIS(int arr[], int n){
    // 配列サイズが0の場合の境界ケースに対応
    vector<int> tailIndices1(n, 0); // 0で初期化
    vector<int> prevIndices1(n, -1); // -1で初期化
    int len1 = 1; // 常に空の場所を指すようにする
    for (int i = 1; i < n; i++) {
        // 新しい最小値が現れた場合
        if (arr[i] < arr[tailIndices1[0]])
            tailIndices1[0] = i;
        // arr[i]が現時点で最大の部分列を延長できる場合
        else if (arr[i] > arr[tailIndices1[len1 - 1]]) {
            prevIndices1[i] = tailIndices1[len1 - 1];
            tailIndices1[len1++] = i;
        }
        // arr[i]が将来の部分列の候補となる場合
        // tailIndices内のceil値を置き換える
        else {
            int pos1 = GetCeilIndex(arr, tailIndices1, -1,
            len1 - 1, arr[i]);
            prevIndices1[i] = tailIndices1[pos1 - 1];
            tailIndices1[pos1] = i;
        }
    }
    // LIS(最長増加部分列)をベクターに格納
    for (int i = tailIndices1[len1 - 1]; i >= 0; i =
        prevIndices1[i])
        res1.push_back(arr[i]);
}

// 最長ビットニック列を求める関数
void longestBitonic(int arr1[], int n1, int arr2[], int n2){
    // 配列1のLISを求める
    LIS(arr1, n1);
    // resを反転して1つ目の配列のLISを正しい順序に整える
    reverse(res1.begin(), res1.end());
    // 配列2を反転してからLISを求める(=最長減少部分列)
    reverse(arr2, arr2 + n2);
    LIS(arr2, n2);
    // 結果を出力
    for (int i = 0; i < res1.size(); i++)
        cout << res1[i] << " ";
}

// ドライバープログラム
int main(){
    cout<<"Example:"<< endl;
    int arr1[] = {3, 1, 2, 4, 5};
    int arr2[] = {6, 4, 3, 2};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
    longestBitonic(arr1, n1, arr2, n2);
    return 0;
}

実行結果

Example:
1 2 4 5 6 4 3 2

計算量について

このアルゴリズムは、各配列に対して二分探索を用いたLISを1回ずつ計算するため、時間計算量はO(n1 log n1 + n2 log n2)となります。また、補助配列としてtailIndicesとprevIndicesを保持するため、空間計算量はO(n1 + n2)です。

まとめ

2つの配列から最長ビットニック列を構成する問題は、LISアルゴリズムを応用することで効率的に解くことができます。ポイントは、1つ目の配列から最長増加部分列を、2つ目の配列(反転後)から最長減少部分列をそれぞれ求め、それらを連結するだけというシンプルさです。動的計画法によるO(n²)の解法と比べて、二分探索を使うことで大規模な入力にも対応できる点が大きなメリットといえます。