【Python】リスト内のすべての部分リストの最小値の合計を効率的に求める方法

問題概要

数値のリスト nums が与えられたとします。このとき、nums から作れるすべての連続する部分リスト（サブリスト）x について最小値を求め、それらの合計を計算します。答えが非常に大きくなる可能性があるため、最終的な結果は 10⁹ + 7 で割った余りを返します。

具体例

たとえば、入力が nums = [5, 10, 20, 10, 0] の場合、出力は 90 になります。これは、考えられる部分リストが次の15通りあり、

[[5], [10], [20], [10], [0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0], [5,10,20,10], [10,20,10,0], [5,10,20,10,0]]

それぞれの最小値が [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0] となり、その合計が 90 になるためです。

解法のポイント：単調スタックによる効率化

すべての部分リストを実際に列挙して最小値を足し合わせる素朴な方法では、計算量が O(n²) を超えてしまい、リストが長い場合に非現実的になります。そこで単調スタック（Monotonic Stack）を利用すると、O(n) の時間計算量でこの問題を解くことができます。

基本的な考え方は、「各時点での累積的な最小値の寄与」をスタックで管理するというものです。スタックの各要素は [インデックス, 値, 貢献度] の3つの情報を持ち、新しい要素がスタック末尾の値以下になったタイミングで、古い要素の貢献度をまとめて引き継ぐことで重複計算を避けています。

アルゴリズムの手順

• ans := 0（答えの合計）、s := 空のスタック、temp_sum := 0（現在までの累積寄与）として初期化します。
• nums の各インデックス index と値 value に対して、以下を繰り返します。
  • スタック s が空でなく、かつ value がスタック末尾要素の値以下である間、次を繰り返します。
    • temp_sum からスタック末尾要素の第3成分（貢献度）を減算します。
    • スタックから末尾要素を削除（ポップ）します。
  • スタック s が空の場合は、[index, value, (index + 1) × value] をスタックに追加します。
  • それ以外の場合は、[index, value, (index − スタック末尾要素のインデックス) × value] をスタックに追加します。
  • temp_sum にスタック末尾要素の第3成分を加算します。
  • ans に temp_sum を加算します。
• 最後に、ans を 10⁹ + 7 で割った余りを返します。

Python実装例

以下が実際の実装コードです。

def solve(nums):
    ans = 0
    s = []
    temp_sum = 0
    for index, value in enumerate(nums):
        while s and value <= s[-1][1]:
            temp_sum -= s[-1][2]
            s.pop()
        if not s:
            s.append([index, value, (index + 1) * value])
        else:
            s.append([index, value, (index - s[-1][0]) * value])
        temp_sum += s[-1][2]
        ans += temp_sum
    return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

実行結果

入力：

[5, 10, 20, 10, 0]

出力：

90

計算量について

このアルゴリズムでは、各要素がスタックに最大1回 push され、最大1回 pop されるだけなので、全体の時間計算量は O(n)、必要なメモリも O(n) で抑えられます。部分リストを全列挙する O(n²)・O(n³) のアプローチと比べ、大きな入力でも高速に動作するのが大きな利点です。