Pythonでコインを労働者に配布する方法の数を数えるプログラム

コインと給与と呼ばれる正の数の2つのリストがあるとします。ここで、coins [i]はコインiの値を示し、salaries[j]はワーカーjに支払う必要のある最低の給与額を示します。ここで、タイプごとに1つのコインがあり、各ワーカーに正確に1つのコインを与える必要があるとすると、各ワーカーにコインを与える方法の数を計算する必要があります。ここで、ある労働者が1つの方法である種類のコインを受け取り、別の方法で別の種類のコインを受け取る場合、2つの方法は異なります。結果が非常に大きい場合は、結果mod 10 ^ 9+7を返します。

したがって、入力がcoins =[1、2、3]、salaries =[1、2]の場合、最初のコイン（値1）を使用しないかのように、出力は4になり、両方のコインは次のようになります。両方の労働者に有効であるため、労働者に支払う方法は2つあります。これで、最初のコインを使用すると、最初のワーカーにのみ送られ、残りのコインのいずれかを使用して2番目のワーカーに支払うことができます。したがって、4つの方法があります。

これを解決するには、次の手順に従います-

• リストコインを並べ替え、リスト給与を並べ替える
• num_coins：=コインのサイズ
• num_salaries：=給与のサイズ
• dp：=新しいマップ
• 給与の各給与について、
  • l：=0、r：=num_coins-1
  • idx：=num_coins
  • l <=rの場合、do
    • m：=l +（r --l）/ 2
    • coins [m]> =給与の場合、
      • idx：=m
      • r：=m-1
    • それ以外の場合、
      • l：=m + 1
  • idxがnum_coinsと同じ場合、
    • 0を返す
  • dp [salary]：=idx
• res：=1
• num_salaries-1から0の範囲のiの場合、1ずつ減らします。
  • 給与：=給与[i]
  • idx：=dp [salary]
  • res：=res *（num_coins --idx + 1）-（num_salaries --i）
• return res mod 10 ^ 9 + 7

理解を深めるために、次の実装を見てみましょう-

例

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