C++でペアの最大長チェーンを求める方法(動的計画法)

問題の概要

ペアのチェーンが与えられます。各ペアは2つの整数から構成されており、最初の整数は必ず2番目の整数より小さくなっています。チェーンの構築にも同じルールが適用され、ペア (x, y) をペア (p, q) の後に連結できるのは、q < x が成り立つ場合のみです。

この問題は、最長増加部分列(LIS)と同じ考え方を応用した動的計画法で効率的に解くことができます。解法の手順は以下のとおりです。

1. 与えられたペアを、最初の要素の昇順にソートします。
2. 各ペアについて、それ以前のペアの2番目の要素と比較します。arr[i].a > arr[j].b が成り立つ場合、ペア j のチェーンの末尾にペア i を連結できます。
3. 各位置で作れる最大チェーン長を記録し、最後にその最大値を求めます。

入力 − 数値ペアのチェーン。{(5, 24), (15, 25), (27, 40), (50, 60)}

出力 − 条件を満たすチェーンの最大長。この例では {(5, 24) → (27, 40) → (50, 60)} の3つのペアが連結できるため、長さは 3 となります。

アルゴリズム

maxChainLength(arr, n)
チェーンの各要素は a と b の2つの値を持つ
入力: ペアの配列と配列内の要素数
出力: チェーンの最大長
Begin
    サイズ n の maxChainLen 配列を定義し、すべて 1 で初期化する
    max := 0
    for i := 1 to n, do
        for j := 0 to i-1, do
            if arr[i].a > arr[j].b かつ maxChainLen[i] < maxChainLen[j] + 1
                maxChainLen[i] := maxChainLen[j] + 1
        done
    done
    max := maxChainLen 配列内の最大値
    return max
End

C++による実装例

#include<iostream>
#include<algorithm>
using namespace std;
struct numPair{ //ペアを構造体として定義
    int a;
    int b;
};
int maxChainLength(numPair arr[], int n){
    int max = 0;
    int *maxChainLen = new int[n]; //サイズ n の配列を作成
    for (int i = 0; i < n; i++ ) //全インデックスのチェーン長を 1 で初期化
        maxChainLen[i] = 1;
    for (int i = 1; i < n; i++ )
        for (int j = 0; j < i; j++ )
            if ( arr[i].a > arr[j].b && maxChainLen[i] < maxChainLen[j] + 1)
                maxChainLen[i] = maxChainLen[j] + 1;
                // maxChainLen[i] にはペア i で終わる最大チェーン長が格納される
    for (int i = 0; i < n; i++ )
        if ( max < maxChainLen[i] )
            max = maxChainLen[i]; //チェーン長の最大値を求める
    delete[] maxChainLen; //メモリを解放
    return max;
}
int main(){
    struct numPair arr[] = {{5, 24},{15, 25},{27, 40},{50, 60}};
    int n = 4;
    cout << "Length of maximum size chain is " << maxChainLength(arr, n);
}

実行結果

Length of maximum size chain is 3

このプログラムでは、動的計画法により「各ペアを終点とする最大チェーン長」を順に計算しています。計算量は O(n²) であり、ペアの数がそれほど多くない場合に有効な手法です。チェーンの構築条件 q < x を満たす組み合わせだけが更新されるため、条件を満たす最長の連結列を正しく求められます。