PythonでLCMがK以下となる最長部分列（サブシーケンス）を見つける方法

問題の概要

互いに異なる n 個の数値からなる配列 A と、正整数 K が与えられたとします。このとき、最小公倍数（LCM）が K 以下となる最長の部分列（サブシーケンス）を配列から見つけます。条件を満たす部分列が存在する場合は、その LCM の値・部分列の長さ・要素のインデックス（0始まり）を出力し、存在しない場合は -1 を返します。

例として、入力が A = [3, 4, 5, 6]、K = 20 の場合を考えてみましょう。このとき出力は次のようになります。

• LCM = 12
• 長さ = 3
• インデックス = [0, 1, 3]

これは、配列の 0 番目・1 番目・3 番目にある「3, 4, 6」を選んだとき、その LCM が 12 となり、K = 20 を超えない中で最も多くの要素を含められるためです。

解法のアルゴリズム

この問題は、各候補となる LCM の値ごとに「何個の要素で構成できるか」を効率的に数え上げることで解決できます。手順は以下の通りです。

1. n を配列 A のサイズとします。
2. 辞書 my_dict を用意し、配列内の各値の出現回数を記録します。
3. サイズ (k + 1) の配列 count を作成し、すべて 0 で初期化します。count[i] は「LCM が i となる場合に使える要素数」を表します。
4. my_dict の各キー key について、key が k 以下であれば、key の倍数（key × i ≤ k）すべてに対して count[key × i] に my_dict[key] を加算します。これは、key が LCM の約数であるならば、その LCM の候補に含められることを意味します。
5. key が k を超える場合はループを抜けます。
6. lcm := 0、size := 0 と初期化した後、i を 1 から k まで走査し、count[i] > size となるところで size と lcm を更新します。これにより、最大の要素数を持つ LCM が求まります。
7. lcm が 0 のままの場合、条件を満たす部分列が存在しないため -1 を返します。
8. それ以外の場合は、lcm と size を表示し、さらに配列 A を走査して「lcm を A[i] で割った余りが 0」となるインデックス i をすべて出力します。

Pythonでの実装例

以下に、上記のアルゴリズムを実装したPythonコードを示します。

from collections import defaultdict

def get_seq(A, k):
    n = len(A)
    my_dict = defaultdict(lambda: 0)
    for i in range(0, n):
        my_dict[A[i]] += 1

    count = [0] * (k + 1)
    for key in my_dict:
        if key <= k:
            i = 1
            while key * i <= k:
                count[key * i] += my_dict[key]
                i += 1
        else:
            break

    lcm = 0
    size = 0
    for i in range(1, k + 1):
        if count[i] > size:
            size = count[i]
            lcm = i

    if lcm == 0:
        print(-1)
    else:
        print("LCM = {0}, Length = {1}".format(lcm, size))
        print("Index values: ", end="")
        for i in range(0, n):
            if lcm % A[i] == 0:
                print(i, end=" ")

k = 20
A = [3, 4, 5, 6]
get_seq(A, k)

入力

[3, 4, 5, 6], 20

出力

LCM = 12, Length = 3
Index values: 0 1 3

計算量について

このアルゴリズムの計算量を確認しておきましょう。各要素 key に対して、その倍数を k 以下の範囲で走査するため、全体の計算量は調和級数の和に基づき O(n log k) + O(k) 程度となります。ここで n は配列の要素数、k は与えられた上限値です。素朴にすべての部分列を列挙する方法（指数時間）と比べると、非常に効率的なアプローチであることがわかります。

まとめ

本記事では、配列から LCM が K 以下となる最長部分列を見つける問題を、倍数テーブルを活用した効率的な手法で解く方法を紹介しました。ポイントは以下の3点です。

• 各値の出現回数を辞書で管理する
• 各値の倍数ごとに使える要素数を累積していく
• 最終的に要素数が最大となる LCM を選び、対応するインデックスを出力する

この手法は、競技プログラミングやデータ分析において「公倍数に関する集合の最適化」を扱う際に応用できる汎用的なパターンです。ぜひ実際のコードで動かしてみてください。