Pythonでコインを労働者に配る組み合わせの総数を求めるプログラム

問題の概要

正の整数からなる2つのリスト coins と salaries が与えられます。coins[i] は i 番目のコインの価値を、salaries[j] は j 番目の労働者に支払うべき最低金額を表します。各種類のコインは1枚ずつしかなく、すべての労働者にちょうど1枚ずつコインを渡す必要があります。このとき、コインの配り方が何通りあるかを計算してください。ある労働者に渡されるコインの種類が異なる場合、その2つの配り方は「異なる」とみなします。答えが非常に大きくなる可能性があるため、結果は 10⁹+7 で割った余りを返します。

例として、coins = [1, 2, 3]、salaries = [1, 2] の場合を考えてみましょう。このときの出力は 4 になります。

• 価値1のコインを使わない場合： 残りの2枚（価値2と3）はどちらも両方の労働者に渡せるため、2通りの支払い方法があります。
• 価値1のコインを使う場合： このコインを受け取れるのは最初の労働者だけです。残りの2枚のうちどちらか1枚を2人目の労働者に渡せるので、さらに2通りあります。

これらを合わせると、合計4通りの配り方が存在することになります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• リスト coins と salaries をそれぞれ昇順にソートする
• num_coins := coins の要素数、num_salaries := salaries の要素数とする
• dp := 新しい辞書（マップ）を作成する
• salaries の各要素 salary に対して、二分探索により coins 内で salary 以上となる最初のインデックス idx を求める
• idx が num_coins と等しい場合（条件を満たすコインが1枚も存在しない場合）、0 を返す
• dp[salary] := idx として記録する
• res := 1 で初期化し、i を num_salaries − 1 から 0 まで減らしながら繰り返す
  　・salary := salaries[i]、idx := dp[salary] とする
  　・res := res × ((num_coins − idx + 1) − (num_salaries − i)) で更新する
• 最後に res mod 10⁹+7 を返す

このアルゴリズムのポイントは、給与条件が厳しい労働者（金額の大きい順）から処理することです。給与条件を満たすコインの候補数から、すでに割り当て済みの労働者の数を差し引くことで、その労働者が実際に選べるコインの選択肢の数が求まります。二分探索を用いることで、各給与に対する探索を O(log n) で効率的に行えます。

実装例

より理解を深めるために、以下のPython実装を見てみましょう。

class Solution:
   def solve(self, coins, salaries):
      coins.sort()
      salaries.sort()
      num_coins = len(coins)
      num_salaries = len(salaries)
      dp = {}
      for salary in salaries:
         l = 0
         r = num_coins - 1
         idx = num_coins
         while l <= r:
            m = l + (r - l) // 2
            if coins[m] >= salary:
               idx = m
               r = m - 1
            else:
               l = m + 1
         if idx == num_coins:
            return 0
         dp[salary] = idx
      res = 1
      for i in range(num_salaries - 1, -1, -1):
         salary = salaries[i]
         idx = dp[salary]
         res *= (num_coins - idx + 1) - (num_salaries - i)
      return res % (10**9+7)
ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries))

入力

[1, 2, 3],[1, 2]

出力

4

このように、ソートと二分探索を組み合わせた貪欲的なアプローチにより、全ての労働者に条件を満たすコインを配る方法の総数を効率的に求めることができます。