Pythonで2つの配列の合計を等しくするために必要な最小限の操作を見つけるプログラム

問題概要

2つのリスト nums1 と nums2 が与えられ、それぞれの要素は 1 以上 6 以下の整数です。ここで、「どちらかのリストから1つの数を選び、その値を 1〜6 の範囲内の任意の数に更新する」という操作を考えます。この操作を繰り返して2つの配列の合計値を等しくするとき、必要な最小の操作回数を求めてください。どうしても等しくできない場合は -1 を返します。

例えば、nums1 = [1, 4]、nums2 = [5, 4, 4] が入力された場合、答えは 2 になります。まず nums1 の 1 を 6 に変更すれば nums1 の合計は 10 になり、次に nums2 の 4 のうちどれか1つを 1 に変更すれば nums2 の合計も 10 となり、両者の合計が一致します。

解法アプローチ：貪欲法

この問題は貪欲法（グリーディ法）を用いることで効率的に解けます。各操作で得られる変化量が最大となる選択を毎回行うのがポイントです。手順は以下の通りです。

• nums1 の合計 sa と nums2 の合計 sb を求めます。
• sa > sb の場合は、nums1 と nums2（および sa と sb）を入れ替えます。これにより、常に nums1 の方が合計が小さい状態になります。
• nums1 を昇順にソートします。小さい値ほど 6 に変更したときの増加量（6 − 値）が大きくなるため、効果の高いものから優先的に使えます。
• nums2 を降順にソートします。大きい値ほど 1 に変更したときの減少量（値 − 1）が大きくなるため、こちらも効果の高いものから使います。
• 差分 toadd = sb − sa を埋めるため、ループの中で毎回「nums1 の値を上げた場合の増加量」と「nums2 の値を下げた場合の減少量」を比較し、より大きい方の操作を適用して toadd から差し引きます。操作のたびにカウンタ res を1ずつ増やします。
• 片方のリストを使い切った場合は、残りのリストだけで差分を埋め続けます。
• 両方のリストを使い切っても toadd が 0 より大きいままなら、解が存在しないため -1 を返します。

このアルゴリズムの計算量は、ソート部分が支配的となるため O(n log n) です。

実装例

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

def solve(nums1, nums2):
    sa = sum(nums1)
    sb = sum(nums2)
    if sa > sb:
        nums1, nums2 = nums2, nums1
        sa, sb = sb, sa

    nums1.sort()
    nums2.sort(reverse=True)
    res = 0
    toadd = sb - sa
    i = 0
    j = 0
    while toadd > 0:
        res += 1
        if i < len(nums1) and j < len(nums2):
            resa = 6 - nums1[i]
            resb = nums2[j] - 1
            if resa > resb:
                toadd -= resa
                i += 1
            else:
                toadd -= resb
                j += 1
        elif i < len(nums1):
            resa = 6 - nums1[i]
            toadd -= resa
            i += 1
        elif j < len(nums2):
            resb = nums2[j] - 1
            toadd -= resb
            j += 1
        else:
            return -1

    return res

nums1 = [1, 4]
nums2 = [5, 4, 4]
print(solve(nums1, nums2))

入力

nums1 = [1, 4]
nums2 = [5, 4, 4]

出力

2

まとめ

本記事では、要素が 1〜6 の範囲にある2つの配列の合計を等しくするための最小操作回数を求めるPythonプログラムを紹介しました。貪欲法により、毎回最も効果の大きい操作を選ぶことで最小回数を達成でき、計算量は O(n log n) と効率的です。同様の「差分を最小ステップで埋める」タイプの問題では、ソートと貪欲法の組み合わせが有効なアプローチになるので、ぜひ覚えておきましょう。