Pythonで繰り返し整数を分配できるか判定するプログラムの実装方法

問題の概要

配列 nums があるとします。この配列には最大50種類の一意な値が含まれています。さらに、quantity という別の配列も与えられ、quantity[i] は i 番目の顧客が注文した数量を表します。ここで、次の条件をすべて満たすように nums を分配できるかどうかを判定する必要があります。

• i 番目の顧客は、ちょうど quantity[i] 個のアイテムを受け取ること
• i 番目の顧客が受け取るアイテムの値は、すべて同じであること
• すべての顧客が満足すること

たとえば、入力が nums = [5,1,2,2,3,4,4,3,3]、quantity = [2,2,3] の場合、出力は True になります。これは、2個ずつ欲しい2人の顧客にそれぞれ [2,2] と [4,4] を渡し、3個欲しい3人目の顧客に [3,3,3] を渡すことで、全員が満足できるからです。

解法のアプローチ(バックトラッキング)

この問題は、バックトラッキング(試行の巻き戻し)を用いて解くのが効果的です。手順は以下の通りです。

• util() 関数の定義： 引数として、現在処理中の顧客番号 i と、各値ごとの残り個数を管理するマップ cntr を受け取ります。
• 終了条件： i が quantity のサイズと等しくなったら、全顧客への割り当てが完了しているため True を返します。
• 状態のコピー： temp_counter として cntr のコピーを作成し、試行ごとに元の状態を汚さないようにします。
• 割り当ての試行： cntr 内の各 cnt(値ごとの残り個数)について、cnt が quantity[i] 以上であれば、その値から quantity[i] 個を顧客 i に割り当てます。残りは rem = cnt − quantity[i] として記録します。
• 再帰とバックトラック： 次の顧客へ再帰的に処理を進め、失敗した場合は状態を元に戻して別の候補を試します。すべての候補が失敗すれば False を返します。

メインの処理では、まず nums 内の各数値の出現回数を求め、さらに「その出現回数」自体の出現回数をカウントしたマップ cnt を作成します。その後、quantity を降順にソートしてから util(0, cnt) を呼び出します。数量の多い注文から先に処理することで、無駄な探索を早い段階で枝刈りでき、計算量を大幅に抑えられるのがポイントです。

Pythonコード例

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

from collections import Counter

def solve(nums, quantity):
    def util(i, cntr):
        if i == len(quantity):
            return True

        temp_counter = cntr.copy()
        for cnt in cntr:
            if cnt >= quantity[i]:
                temp_counter[cnt] -= 1
                if temp_counter[cnt] == 0:
                    temp_counter.pop(cnt)
                rem = cnt - quantity[i]
                temp_counter[rem] += 1

                if util(i + 1, temp_counter):
                    return True

                # バックトラック:状態を元に戻す
                temp_counter[rem] -= 1
                if temp_counter[rem] == 0:
                    temp_counter.pop(rem)
                temp_counter[cnt] += 1

        return False

    cnt = Counter(Counter(nums).values())
    quantity.sort(reverse=True)
    return util(0, cnt)

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

入力と出力の例

別の入力パターンでの動作は以下のようになります。

入力：

[0,1,2,3,4], [[3,1],[1,3],[5,6]]

出力：

True

まとめ

この記事では、重複を含む整数配列を複数の顧客の注文数量どおりに分配できるかを判定するPythonプログラムを紹介しました。collections.Counter で頻度情報を整理しつつ、バックトラッキングによって「同じ値のアイテムだけを各顧客に割り当てる」組み合わせを効率的に探索できます。数量を降順にソートして大きな注文から処理することが、探索範囲を絞る重要な工夫です。