Pythonで数値を合成数の和に分解したときの最大項数を求める方法

整数 N（1 ≤ N ≤ 10^9）が与えられたとき、N をできるだけ多くの合成数（composite number）の和として表現し、その最大の項数を返すことを考えます。もし分解が不可能な場合は -1 を返します。

例えば、入力が 16 の場合、出力は 4 になります。16 は 4 + 4 + 4 + 4 とも 8 + 8 とも表せますが、項数が最大になるのは 4 + 4 + 4 + 4 の4項構成だからです。

解法のアプローチ

この問題は動的計画法（DP）を使うことで効率的に解けます。ポイントは次のとおりです。

• 最小の合成数は 4、続いて 6、9 です。実はすべての合成数は 4・6・9 の組み合わせで表せるため、この3つだけを「コイン」として扱えば十分です。
• N が小さい場合（16 未満）は、事前計算しておいたテーブルから直接答えを取得します。
• N が大きい場合は、余った部分を 4 の和で埋めて拡張します。4 を1つ追加するたびに項数が1増えるためです。

なお、1・2・3・5・7・11 のような数は合成数の和として表せないため、この場合は -1 が返されます。

アルゴリズムの手順

1. max_val := 16 と定義します。
2. 関数 pre_calc() を定義します。
   • サイズ max_val のリスト table を作成し、全要素を -1 で初期化します。
   • table[0] := 0 とします。
   • v := [4, 6, 9]（合成数の候補）とします。
   • i を 1 から max_val 未満まで1ずつ増やしながら、k を 0〜2 について繰り返します。
     • j := v[k]
     • i ≥ j かつ table[i − j] ≠ −1 ならば、table[i] := max(table[i], table[i − j] + 1)
   • table を返します。
3. 関数 max_summ() を定義します（引数は table と n）。
   • n < max_val なら table[n] をそのまま返します。
   • それ以外の場合は、t := int((n − max_val) / 4) + 1 とし、t + table[n − 4 × t] を返します。
4. メイン処理では table := pre_calc() を実行し、max_summ(table, n) の結果を表示します。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

global max_val
max_val = 16

def pre_calc():
    table = [-1 for i in range(max_val)]
    table[0] = 0
    v = [4, 6, 9]
    for i in range(1, max_val, 1):
        for k in range(3):
            j = v[k]
            if (i >= j and table[i - j] != -1):
                table[i] = max(table[i], table[i - j] + 1)
    return table

def max_summ(table, n):
    if (n < max_val):
        return table[n]
    else:
        t = int((n - max_val) / 4) + 1
        return t + table[n - 4 * t]

n = 16
table = pre_calc()
print(max_summ(table, n))

入力

16

出力

4

計算量について

事前計算 pre_calc() の計算量は O(max_val × 3)、つまり定数時間で済みます。また、max_summ() による各クエリへの応答は O(1) であるため、N が最大 10^9 まで大きくなっても高速に答えを求められます。このように、小さい範囲をDPで精密に求め、大きい範囲は周期性（4ずつの拡張）を利用して補完する手法は、競技プログラミングでもよく使われる定石です。