与えられた操作でリストを減らしながら、Pythonで残る最小の数を求めるプログラム

問題の概要

正の整数からなるリスト nums が与えられます。ここで、次のような操作を考えます。

• リストから任意の2つの値 a と b(a ≤ b)を取り除く
• a < b が成り立つ場合、その差 b − a をリストへ挿し戻す

この操作は何回でも実行できます。最終的にリストに残せる最小の数を求めてください。なお、リストが空になった場合は 0 を返します。

入出力例

たとえば nums = [2, 4, 5] の場合、答えは 1 になります。まず 4 と 5 を選んで差の 1 を戻せばリストは [2, 1] となり、続いて 2 と 1 を選べば [1] だけが残ります。

解き方のアプローチ

この問題は、各要素を「足す側」と「引く側」に振り分けたときの差の絶対値の最小値を求める、いわゆる部分和(パーティション)問題と同じ構造を持っています。合計を s とすると、ある部分集合の合計を n としたとき、最終的な残りは s − 2n で表せます。つまり「s − 2n が負にならない範囲で n をできるだけ大きく取る」ことが目標になります。

以下の手順で再帰的に解きます。

• s := nums の全要素の合計
• 関数 f(i, s) を定義する
• i が nums のサイズ以上なら s を返す(ベースケース)
• n := nums[i]
• s − 2 × n < 0 の場合、この要素を引く側に使えないため f(i + 1, s) を返す
• それ以外は f(i + 1, s − 2 × n) と f(i + 1, s) の小さい方を返す
• メイン処理では f(0, s) を返す

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(nums):
    s = sum(nums)

    def f(i, s):
        if i >= len(nums):
            return s
        n = nums[i]
        if s - 2 * n < 0:
            return f(i + 1, s)
        return min(f(i + 1, s - 2 * n), f(i + 1, s))

    return f(0, s)

nums = [2, 4, 5]
print(solve(nums))

入力

[2, 4, 5]

出力

1

計算量と高速化のポイント

この再帰解法は各要素ごとに「使う / 使わない」の2択を試すため、時間計算量は O(2ⁿ)、再帰の深さによる空間計算量は O(n) となります。要素数が多い場合は、メモ化(動的計画法)やビット演算を使った部分和DPに置き換えることで大幅に高速化できます。