Pythonで全コーダーに支払うべき最低報酬額を求めるプログラム

問題の概要

コーダーのパフォーマンススコアを表す数値リスト「ratings」が与えられているとします。マネージャーは各コーダーに最低1,000ルピーを支払いますが、隣接する2人のコーダーが存在する場合、パフォーマンスが優れている方には、劣っている方よりも少なくとも1,000ルピー多く支払いたいと考えています。この制約をすべて満たすとき、マネージャーが支払うべき最小金額を求めるのが目標です。

例えば、入力が ratings = [1, 2, 5, 1] の場合、出力は 7000 になります。これは、各コーダーへの支払額がそれぞれ [1000, 2000, 3000, 1000] となるのが最適だからです。

解法のアプローチ

この問題は、左右両方向からの走査(2パス方式)を使うことで効率的に解けます。手順は以下の通りです。

• pay を ratings と同じサイズのリストとして初期化し、すべての値を 1 に設定します
• i を 1 から ratings のサイズ − 1 まで増加させながら処理します
  • もし ratings[i] > ratings[i−1] なら、pay[i] = pay[i−1] + 1 とします
• 次に i を ratings のサイズ − 2 から 0 まで減少させながら処理します
  • もし ratings[i] > ratings[i+1] なら、pay[i] = max(pay[i], pay[i+1] + 1) とします
• 最後に (pay の要素の合計) × 1000 を返します

最初の左から右への走査では昇順の並びに対する制約を満たし、次の右から左への走査では降順の並びに対する制約を補完します。これにより、すべての隣接ペア間の条件を確実に満たすことができます。

Pythonでの実装例

それでは、理解を深めるために実際のコードを見てみましょう。

class Solution:
    def solve(self, ratings):
        pay=[1 for _ in ratings]
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i-1]:
                pay[i] = pay[i-1]+1
        for i in range(len(ratings)-2,-1,-1):
            if ratings[i] > ratings[i+1]:
                pay[i] = max(pay[i], pay[i+1]+1)
        return sum(pay)*1000
ob = Solution()
ratings = [1, 2, 5, 1]
print(ob.solve(ratings))

入力

[1, 2, 5, 1]

出力

7000

このアルゴリズムの計算量は O(n)、空間計算量も O(n) であり、リストの長さに対して線形の効率で動作します。