Pythonで順列の中からリクエスト合計が最大になる並べ方を見つける方法

問題の概要

配列 nums と、リクエストを表す配列 requests があります。requests[i] = [start_i, end_i] は、i 番目のリクエストが nums[start_i] + nums[start_i+1] + ... + nums[end_i] の総和を求めることを意味します。ここで、nums のすべての順列の中から、全リクエストの合計が最大になる並べ方を見つけます。答えは非常に大きな数になる可能性があるため、10⁹+7 で割った余りを返します。

たとえば、入力が nums = [10,20,30,40,50]、requests = [[1,3],[0,1]] の場合、出力は 190 になります。[30,50,40,20,10] のように並べ替えると、次のように計算できます。

• requests[0]：nums[1] + nums[2] + nums[3] = 50 + 40 + 20 = 110
• requests[1]：nums[0] + nums[1] = 30 + 50 = 80

したがって、合計は 110 + 80 = 190 となります。

解法のポイント

この問題を効率よく解く鍵は、「ある位置がいくつのリクエスト区間に含まれるか（被覆回数）」を求め、被覆回数が多い位置ほど大きい値を割り当てるという貪欲法です。区間の開始と終了をイベントとして扱い、ソート後に一括で走査することで、各被覆回数に対応するインデックス範囲をまとめて記録できます。

アルゴリズムの手順

1. 空のリスト A を作成します。
2. requests 内の各リクエスト (s, e) について、A に開始マーカー (s, 0) と終了マーカー (e, 1) を追加します。
3. A をソートします。
4. 被覆回数を記録するマップ fr を用意し、カウンタ cnt を 0 で初期化します。
5. ソート済みのイベントを先頭から走査し、同一のイベントが連続する場合はまとめて処理します。
   • 開始イベントの場合：cnt を増やし、直前の被覆回数が正であれば、その回数に対応する範囲 (pre, p-1) を fr に記録して pre を更新します。
   • 終了イベントの場合：cnt を減らし、範囲 (pre, p) を fr に記録して pre を更新します。
6. nums を降順にソートし、fr のキー（被覆回数の一覧）も降順にソートします。
7. 被覆回数が大きい順に、各範囲の長さ d 分だけ残りの大きな値を取り出し、「その合計 × 被覆回数」を答えに加算します（10⁹+7 で剰余を取ります）。
8. 最終的な答えを返します。

実装例（Python）

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

from collections import defaultdict

def solve(nums, requests):
    A = []
    for s, e in requests:
        A.append((s, 0))
        A.append((e, 1))
    A.sort()
    fr = defaultdict(list)
    cnt = 0

    n = len(A)
    i = 0
    while i < n:
        r = 1
        while i < n - 1 and A[i+1] == A[i]:
            r += 1
            i += 1
        p, flag = A[i]
        if flag == 0:
            cnt += r
            if cnt - r > 0:
                fr[cnt-r].append((pre, p-1))
            pre = p
        elif flag == 1:
            cnt -= r
            fr[cnt+r].append((pre, p))
            pre = p+1
        i += 1

    nums.sort(reverse=True)
    ks = list(fr.keys())
    ks.sort(reverse=True)
    ans = 0
    m = 10**9 + 7
    i = 0
    for k in ks:
        for s, e in fr[k]:
            d = e - s + 1
            ans += sum(nums[i:i+d]) * k
            ans %= m
            i += d
    return ans

nums = [10,20,30,40,50]
requests = [[1,3],[0,1]]
print(solve(nums, requests))

入力

[10,20,30,40,50],[[1,3],[0,1]]

出力

190

なぜこの方法で最大になるのか

全リクエストの合計は、「各位置の値 × その位置が含まれる区間の数」の総和として表せます。つまり、より多くの区間に含まれる位置に大きな値を置くほど、全体の合計が大きくなります。大小関係が逆の割り当てを入れ替えると必ず合計が減少するため、この貪欲法が最適であることが分かります。計算量は、イベントのソートと nums のソートが支配的となり、要素数を n、リクエスト数を q とすると O(n log n + q log q) 程度で抑えられます。