【C++】動的計画法で最大の割り切れるペアの部分集合を見つけるプログラム

問題の概要

互いに異なる要素から構成される配列が与えられます。この中から、すべてのペアが割り切れる関係にある部分集合(サブセット)を見つけるのが課題です。つまり、部分集合内のどの大きい要素も、それより小さいすべての要素で割り切れる必要があります。

入力 : arr[] = {10, 5, 3, 15, 20}
出力 : 3
説明 : 最大の部分集合は {10, 5, 20} です。
10は5で割り切れ、20は10で割り切れます。

入力 : arr[] = {18, 1, 3, 6, 13, 17}
出力 : 4
説明 : 最大の部分集合は {18, 1, 3, 6} です。
この列では、3は1で割り切れ、6は3で、18は6で割り切れます。

この問題は動的計画法(DP)を使うことで効率的に解くことができます。以下でその具体的な方法を見ていきましょう。

解法のアプローチ

まず、配列を昇順にソートします。次に、配列の末尾から先頭に向かって走査していきます。その際、dp配列を管理します。dp[i]には「i番目の要素を最小要素とする最大部分集合のサイズ」を格納します。最後に、dp配列の中の最大値を答えとして返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
int largestSubsetPair(int *a, int n){
    int dp[n]; // i番目のインデックスから始まる最大部分集合のサイズを格納
    dp[n - 1] = 1; // 最後の要素が最大なので、その部分集合のサイズは1
    int largest = 0; // 答え
    for (int i = n - 2; i >= 0; i--) {
        int maxi = 0; // 最大値を0で初期化
        for (int j = i + 1; j < n; j++)
            if (a[j] % a[i] == 0 || a[i] % a[j] == 0)
                maxi = max(maxi, dp[j]); // a[j]がa[i]で割り切れる場合
                // a[j]で割り切れる要素もすべて条件を満たす
        dp[i] = 1 + maxi;
        largest = max(largest, dp[i]);
    }
    return largest;
}
int main(){
    int a[] = { 1, 3, 6, 13, 17, 18 }; // 与えられた配列
    int n = sizeof(a) / sizeof(int); // 配列のサイズ
    cout << largestSubsetPair(a, n) << "\n";
    return 0;
}

出力結果

4

コードの解説

このアプローチでは、動的計画法を用いて問題を段階的に解いています。まず配列をソートし、これまで求めた最大部分集合の情報を保存するためのdp配列を用意します。

次に、配列の末尾から逆順に走査します。現在の要素を最小要素と仮定し、その後ろにある倍数を探します。逆順に走査しているため、後方の要素はすでに処理済みであり、「その要素を最小とする最大部分集合のサイズ」がdp配列に記録されています。この値を現在の要素のdp値に加算していくことで、答えを徐々に構築できます。

なお、このアルゴリズムの計算量は二重ループにより時間計算量 O(n²)、dp配列の分だけ空間計算量 O(n)となります。要素数が数千程度までの入力であれば十分実用的です。

まとめ

本記事では、動的計画法を用いて「最大の割り切れるペアの部分集合」を見つける問題を解きました。昇順ソートとDP配列を組み合わせた解法の全体像と、C++での実装例を紹介しました。同じロジックはC、Java、Pythonなど他の言語でもほぼ同様に実装できます。競技プログラミングやコーディング面接でも頻出のテクニックなので、ぜひ理解を深めてください。