C++で最大の割り切り可能サブセット(Largest Divisible Subset)を求める方法

問題の概要

相異なる正整数からなる集合が与えられたとき、次の条件を満たす最大の部分集合(要素数が最も多い部分集合)を見つける問題を考えます。

• 部分集合内の任意の2つの要素のペア (Si, Sj) について、Si % Sj == 0 または Sj % Si == 0 が常に成り立つ

例えば、入力が [1, 2, 3] の場合、[1, 2] または [1, 3] が答えになります(どちらも条件を満たす大きさ2の部分集合です)。

アプローチ：ソート+動的計画法(DP)

この問題は、最長増加部分列(LIS)と同じ発想の動的計画法で効率よく解けます。まず配列を昇順にソートするのがポイントです。ソート済みであれば、nums[i] を割り切れる要素(nums[i] の約数になり得る要素)は必ずインデックス i より前に存在するため、各要素について「それより前の要素」だけを調べれば十分になります。

ここでは次の2つの補助配列を使用します。

• len[i]:nums[i] を末尾とする割り切り可能な部分集合の最大長
• par[i]:その部分集合において nums[i] の直前に来る要素のインデックス(解の復元用)

アルゴリズムの手順

1. 結果を格納する配列 ret を用意し、endpoint := 0、retLen := 1、n := numsのサイズ と初期化する
2. n が 0 の場合は空の集合を返す
3. nums を昇順にソートする
4. 長さ n の配列 len と par を作成し、len はすべて 1、par はすべて 0 で初期化する
5. i を 1 から n − 1 まで繰り返す:
   • par[i] := i とする
   • j を 0 から i − 1 まで繰り返し、「nums[i] % nums[j] == 0 かつ len[j] + 1 > len[i]」を満たすなら、len[i] := len[j] + 1、par[i] := j と更新する
   • len[i] > retLen であれば、retLen := len[i]、endpoint := i と更新する
6. ret に nums[endpoint] を追加する
7. endpoint != par[endpoint] の間、endpoint := par[endpoint] と更新しながら nums[endpoint] を ret に追加していく(親配列をたどって部分集合を復元)
8. ret を逆順に並べ替えて返す

C++での実装例

以下は、上記のアルゴリズムを実装したC++のコードです。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> largestDivisibleSubset(vector<int>& nums) {
      vector <int> ret;
      int endPoint = 0;
      int retLen = 1;
      int n = nums.size();
      if(!n) return {};
      sort(nums.begin(), nums.end());
      vector <int> len(n, 1);
      vector <int> par(n, 0);
      for(int i = 1; i < n; i++){
         par[i] = i;
         for(int j = 0; j < i; j++){
            if(nums[i] % nums[j] == 0 && len[j] + 1 > len[i]){
               len[i] = len[j] + 1;
               par[i] = j;
            }
         }
         if(len[i] > retLen){
            retLen = len[i];
            endPoint = i;
         }
      }
      ret.push_back(nums[endPoint]);
      while(endPoint != par[endPoint]){
         endPoint = par[endPoint];
         ret.push_back(nums[endPoint]);
      }
      reverse(ret.begin(), ret.end());
      return ret;
   }
};
int main(){
   Solution ob;
   vector<int> v = {1,2,3};
   print_vector(ob.largestDivisibleSubset(v));
}

入力

[1,2,3]

出力

[1, 2]

計算量

• 時間計算量:要素同士の比較に二重ループを使うため O(n²)
• 空間計算量:len・par・ret の保持に O(n)

ソートを行うことで「小さい数が大きい数の約数になる」という関係を一方向の走査だけで判定できる点が、この解法の肝です。LIS(最長増加部分列)の変形問題として捉えると、アルゴリズムの構造が理解しやすくなります。