配列内で最大の割り切り可能なサブセットを見つけるC++プログラム

はじめに

本チュートリアルでは、互いに異なる正の整数からなる配列が与えられたとき、任意の2つの要素について「大きい方が小さい方で割り切れる」という条件を満たす、最大のサブセットを見つける問題を解説します。

入力: nums[ ] = { 1, 4, 2, 6, 7}
出力: 1 2 4
説明:
割り切り可能なサブセットには (1, 2, 4)、(1, 2, 6)、(1, 7) などがあります。
条件を満たすペアを持つ長さ3のサブセットが2つ存在します。

入力: nums[ ] = { 1, 2, 3, 6 }
出力: 6 2 1

解決策へのアプローチ

本チュートリアルでは、2つの異なるアプローチについて説明します。

単純なアプローチ（再帰）

単純なアプローチでは、再帰を用いてこの問題を解くことができます。各要素を取り上げ、それをサブセットに含めるべきかどうかを判定していきます。

最初の要素から始めるとしましょう。最初の要素については、「サブセットに含める」か「含めない」かの2つの選択肢があります。最初の要素を含めた場合、2番目の要素をサブセットに追加するには、すでに部分列に含まれている要素（この場合は最初の要素）を割り切れるか、あるいは割り切られる必要があります。この操作を配列全体に対して繰り返します。

この方法では各要素について2通りの選択肢があるため、経路の総数は2^n通りとなり、時間計算量は O(2^n) になります。これは要素数が増えると現実的ではないため、次により効率的なアプローチを見ていきましょう。

効率的なアプローチ（動的計画法）

この問題は、動的計画法（DP）を用いることで効率的に解くことができます。手順は以下の通りです。

• まず配列をソートします。これにより、ある要素が別の要素で割り切れるかどうかの判定を一方向だけで済ませることができます。

• 最長増加部分列（LIS）と同様の考え方で、dp[ ] 配列を用意し、「i番目のインデックスで終わる最大の割り切り可能サブセットのサイズ」を格納します。各要素は自分自身を割り切れるため、すべてのインデックスを1で初期化します。

• 2番目のインデックスから順に反復処理を行い、現在のインデックスで終わる最大の割り切り可能サブセットを求めます。これにより、各インデックスにおける最大サブセットのサイズがわかります。

• 配列を走査しながら、各要素について「割り切り可能なサブセットのサイズが最大となる約数」を探します。見つかった場合は、現在のインデックスのdp値を「その要素のdp値 + 1」に更新します。

C++による実装例

上記の効率的なアプローチを実装したC++コードは以下の通りです。

#include<bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 2, 3, 6};
    int n = sizeof(nums)/sizeof(int);
    // 割り算の判定条件を1つ減らすために配列をソート
    sort(nums, nums+n);
    vector <int> prev_res(n, -1);
    // 各要素の約数（直前のインデックス）を記録するベクトル
    vector <int> dp(n, 1);
    int max = 1;
    for (int i=1; i<n; i++){  // i番目の要素の約数がj番目に存在するか確認
        for (int j=0; j<i; j++){
            if (nums[i]%nums[j] == 0){
            // 追加することでサブセットのサイズが増えるか確認
                if (dp[i] < dp[j] + 1){
                    dp[i] = dp[j]+1;
                    prev_res[i] = j;
                }
            }
        }
        // 最大サイズのサブセットを持つインデックスを更新
        if(max<dp[i])
            max = dp[i];
    }
    cout << "配列内の最大の割り切り可能サブセット: ";
    // 最大のサブセットを出力
    int k = max;
    while (k >= 0){
        cout << nums[k] << " ";
        k = prev_res[k];
    }
    return 0;
}

出力結果

配列内の最大の割り切り可能サブセット: 6 2 1

まとめ

本チュートリアルでは、与えられた配列の中から、任意のペアの整数が互いに割り切れる関係にある最大のサブセットを見つける問題を扱いました。まず再帰を用いたアプローチが指数時間 O(2^n) かかることを確認し、その後、動的計画法を用いた効率的な解法を解説しました。紹介したC++プログラムのロジックは、C、Java、Pythonなどの他のプログラミング言語でも同様に実装できます。本チュートリアルが皆さまの学習に役立てば幸いです。