Pythonでソート済み部分配列の合計から指定範囲の合計を求めるプログラム

問題の概要

正の整数を n 個含む配列 nums があるとします。nums のすべての空でない連続する部分配列について合計値を計算し、それらを昇順(非減少順)に並べ替えると、n*(n+1)/2 個の数値からなる新しい配列が得られます。この新しい配列の中から、left 番目から right 番目まで(1始まり・両端を含む)の要素の合計を求めるのが目的です。

答えは非常に大きな値になる可能性があるため、結果は 10^9 + 7 で割った余りを返します。

入力例

たとえば、nums = [1,5,2,6]、left = 1、right = 5 という入力を考えてみましょう。

すべての部分配列の合計は「1, 5, 2, 6, 6, 7, 8, 8, 13, 14」であり、これをソートすると [1, 2, 5, 6, 6, 7, 8, 8, 13, 14] になります。1番目から5番目までの要素の合計は 1+2+5+6+6 = 20 となるため、出力は 20 です。

解法のアプローチ

この問題は、以下の手順に従って解くことができます。

• m := 10^9 + 7 とする。
• n := 配列 nums のサイズとする。
• a := 新しい空のリストを用意する。
• i を 0 から n-1 まで繰り返す。
  • j を i から n-1 まで繰り返す。
    • i と j が等しい場合(部分配列の先頭):a の末尾に nums[j] を追加する。
    • それ以外の場合:a の末尾に (nums[j] + a の最後の要素) mod m を追加する。
• リスト a をソートする。
• sm := a[left-1 : right] の全要素の合計とする。
• sm mod m を返す。

ポイントは、内側のループで「直前に計算した累積値」に次の要素を加えていくことで、開始位置 i を固定したときの各部分配列の合計を効率よく生成できる点です。

実装例(Python)

理解を深めるために、以下の実装例を見てみましょう。

def solve(nums, left, right):
    m = 10**9 + 7
    n = len(nums)
    a = []
    for i in range(n):
        for j in range(i, n):
            if i == j:
                a.append(nums[j])
            else:
                a.append((nums[j] + a[-1]) % m)
    a.sort()
    sm = sum(a[left-1:right])
    return sm % m

nums = [1, 5, 2, 6]
left = 1
right = 5
print(solve(nums, left, right))

入力

[1, 5, 2, 6], 1, 5

出力

20

計算量について

部分配列の合計は全部で n*(n+1)/2 個生成されるため、リストの構築には O(n²)、その後のソートには O(n² log n) の時間計算量がかかります。n が大きいケースでは、累積和や二分探索を組み合わせた最適化も検討できますが、まずはこのシンプルな実装で問題の構造をつかむのがおすすめです。