Pythonで接頭辞和がすべて正になるように先頭へ挿入する最小の値を求めるプログラム

数値のリスト nums が与えられたとします。このリストの先頭に挿入することで、結果として得られるリストの接頭辞和（プレフィックスサム）がすべて0より大きくなるような、最小の正の値を求めるのがこの問題の目的です。

問題の例

たとえば、入力が nums = [3, -6, 4, 3] の場合、出力は 4 になります。これは、4 をリストの先頭に挿入すると [4, 3, -6, 4, 3] となり、その接頭辞和は [4, 7, 1, 5, 8] となって、すべての値が0より大きくなるためです。

解法のアプローチ

この問題は、次の手順で効率的に解くことができます。

• リスト nums の先頭（インデックス0）に 0 を挿入します。
• インデックス1からリストの末尾まで順に走査し、各要素に対して nums[i] = nums[i] + nums[i - 1] を実行して累積和（接頭辞和）を計算します。
• 最後に 1 - min(nums) を返します。これにより、接頭辞和の最小値がちょうど1になるように調整した値、つまり必要な最小の正の整数が得られます。

Pythonでの実装例

以下のコードで実際の動作を確認してみましょう。

def solve(nums):
   nums.insert(0, 0)
   for i in range(1, len(nums)):
      nums[i] += nums[i - 1]
   return 1 - min(nums)

nums = [3, -6, 4, 3]
print(solve(nums))

入力

[3, -6, 4, 3]

出力

4

アルゴリズムのポイント

この手法の鍵となるのは、先頭に挿入すべき値 x を加えたとき、すべての接頭辞和に一律に x が加算されるという性質です。元のリストの接頭辞和の最小値を m とすると、x + m > 0 を満たす最小の正の整数 x は 1 - m となります。計算量は O(n) と非常に効率的で、大きなリストでも高速に処理できます。