Pythonで「すべてのペアが互いに割り切れる」最大サブセットのサイズを求めるプログラム

問題の概要

重複しない数値のリスト nums が与えられたとします。このとき、サブセット内の任意の2つの要素のペア (i, j) について、「i % j = 0」または「j % i = 0」のどちらかが必ず成り立つような最大のサブセットを見つけ、そのサイズを返すのが目的です。

例えば、入力が nums = [3, 6, 12, 24, 26, 39] の場合、出力は 4 となります。これは、最大の有効なサブセットが [3, 6, 12, 24] になるためです(3 → 6 → 12 → 24 と、すべての隣接する要素同士が割り切れる関係になっています)。

解法の考え方(動的計画法)

この問題は、動的計画法(DP)を使うことで効率的に解くことができます。基本的な発想は「最長増加部分列(LIS)」と似ています。

• リストを昇順にソートしておくことで、ある要素より前の要素だけを約数候補としてチェックすればよくなります。
• dp[i] を「nums[i] を末尾とする有効なサブセットの最大サイズ」と定義します。初期値はすべて 1 です(自分自身だけで構成される場合)。
• i より小さい各 j について nums[i] % nums[j] == 0(割り切れる)ならば、dp[i] = max(dp[i], dp[j] + 1) で更新できます。

アルゴリズムの手順

• dp:リスト nums と同じサイズの配列を作り、すべて 1 で初期化します。
• リスト nums を昇順にソートします。
• n:リストのサイズを取得します。
• n <= 1 の場合はそのまま n を返します。
• ans を 0 で初期化します。
• i を 1 から n 未満まで繰り返し:
  • j を 0 から i 未満まで繰り返し:
    • nums[i] が nums[j] で割り切れる場合、dp[i] を dp[i] と dp[j] + 1 の大きい方で更新します。
  • ans を ans と dp[i] の大きい方で更新します。
• 最後に ans を返します。

Pythonでの実装例

以下が実際の実装コードです。

class Solution:
   def solve(self, nums):
      dp = [1] * len(nums)
      nums.sort()
      n = len(nums)
      if n <= 1:
         return n
      ans = 0
      for i in range(1, n):
         for j in range(0, i):
            if nums[i] % nums[j] == 0:
            dp[i] = max(dp[i], dp[j] + 1)
         ans = max(ans, dp[i])
      return ans
ob = Solution()
nums = [3, 6, 12, 24, 26, 39]
print(ob.solve(nums))

入力

[3, 6, 12, 24, 26, 39]

出力

4

計算量について

このアルゴリズムの時間計算量は二重ループにより O(n²) です(n はリストの要素数)。空間計算量はDP配列分の O(n) となります。ソートを行うことで、割り切れる関係の判定を前方の要素に限定でき、正しくDPを適用できるのがポイントです。