Pythonで隣接ペアの合計をk以下に抑えるための最小操作回数を求めるプログラム

問題概要

負でない数値のリスト nums と、負でない整数 k が与えられます。ここで、「リスト内の正の数を1つ選び、その値を1だけ減らす」という操作を何度でも行えるものとします。すべての隣接する要素のペアの合計が k 以下になるようにするために必要な最小の操作回数を求めてください。答えが非常に大きくなる可能性がある場合は、結果を 10^9 + 7 で割った余りを返します。

たとえば、入力が nums = [4, 6, 2, 5]、k = 6 の場合、出力は 5 になります。これは、リストを [3, 3, 1, 4] に変形すれば、合計5回の減算操作ですべての隣接ペアの合計が 6 以下に収まるからです。

解法のアプローチ

この問題は貪欲法（グリーディー法）で効率的に解くことができます。リストを左から右へ走査しながら、各隣接ペアの合計が k を超えている場合、その超過分だけ右側の要素を減らしていきます。こうすることで、左側の要素をそのまま維持でき、以降のペアへの影響も考慮した最小限の操作が可能になります。

具体的な手順は次のとおりです。

• m = 10^9 + 7 を定義します。
• 操作回数のカウンタ ans = 0 を初期化します。
• i を 0 から len(nums) - 2 まで繰り返します。
  • sm = nums[i] + nums[i+1]（隣接ペアの合計）を計算します。
  • diff = max(sm - k, 0) で、k を超えている分だけを求めます。
  • nums[i+1] -= diff として右側の要素を減らします。
  • もし nums[i+1] < 0 になった場合は、nums[i+1] = 0 に丸めます。
  • ans += diff で操作回数を加算します。
• 最後に ans % m を返します。

実装例

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

m = 10 ** 9 + 7

class Solution:
    def solve(self, nums, k):
        ans = 0
        for i in range(0, len(nums) - 1):
            sm = nums[i] + nums[i + 1]
            diff = max(sm - k, 0)
            nums[i + 1] -= diff
            if nums[i + 1] < 0:
                nums[i + 1] = 0
            ans += diff
        return ans % m

ob = Solution()
nums = [4, 6, 2, 5]
k = 6
print(ob.solve(nums, k))

入力

[4, 6, 2, 5], 6

出力

5

まとめ

このアルゴリズムはリストを一度走査するだけで済むため、時間計算量は O(n)、追加のメモリ使用量は O(1) という非常に効率的な解法です。貪欲に右側の要素を削っていくことで、常に最適な操作回数が得られる点がポイントです。