概要

\(N\) 個の果物から、売値の最大値と最小値の差が \(D\) 以下になるように1個以上選び、利益（売値 − 仕入れ値）の合計を最大化する問題です。売値でソートした上で尺取り法（スライディングウィンドウ）を使って効率的に解きます。

考察

重要な気づき

観察1: 売値でソートすると制約が扱いやすくなる

売値の最大値と最小値の差が \(D\) 以下という条件は、果物を売値 \(P_i\) の昇順にソートすると、「連続する区間 \([l, r]\) で \(P[r] - P[l] \leq D\)」という形に変換できます。選ぶ果物の売値は必ずこのような区間内に収まるからです。

観察2: 有効なウィンドウ内での最適な選び方

ある有効な区間（\(P[r] - P[l] \leq D\) を満たす区間）が決まったとき、その中からどの果物を選ぶのが最適でしょうか？

• 利益が正の果物：選べば合計利益が増えるので、全て選ぶべき
• 利益が0以下の果物：選ぶと合計利益が減る（または変わらない）ので、選ばない方が良い
• ただし、区間内に利益が正の果物が1つもない場合、少なくとも1個選ぶ義務があるので、最も利益が大きい（損失が小さい）果物を1つだけ選ぶ

素朴なアプローチの問題

全ての部分集合を試すと \(O(2^N)\) で到底間に合いません。全ての区間 \([l, r]\) について各果物を調べると \(O(N^2)\) となり、\(N = 2 \times 10^5\) では厳しいです。

解決策

尺取り法を使えば、有効な区間を \(O(N)\) 個列挙しながら、各区間での「正の利益の合計」と「最大利益」を効率的に管理できます。

アルゴリズム

1. 各果物について \((P_i, P_i - C_i)\)（売値と利益）のペアを作り、売値の昇順にソートする。
2. 右端 \(r\) を \(0\) から \(N-1\) まで動かしながら、\(P[r] - P[l] > D\) となる限り左端 \(l\) を進める（尺取り法）。
3. ウィンドウ内で以下を管理する：
   • sum_positive: 利益が正の果物の利益合計
   • count_positive: 利益が正の果物の個数
   • SortedList: ウィンドウ内の全利益を管理（最大値を \(O(\log N)\) で取得）
4. 各ウィンドウでの候補値を計算：
   • count_positive > 0 なら sum_positive（正の利益を全て取る）
   • そうでなければ SortedList の最大値（最もマシな1つを選ぶ）
5. 全ウィンドウでの候補値の最大値が答え。

計算量

• 時間計算量: \(O(N \log N)\)（ソートに \(O(N \log N)\)、尺取り法で各要素の追加・削除が SortedList で \(O(\log N)\)）
• 空間計算量: \(O(N)\)（果物の配列と SortedList の分）

実装のポイント

• SortedList の活用: Python の標準ライブラリには平衡二分探索木がないため、sortedcontainers ライブラリの SortedList を使って、ウィンドウ内の最大利益を効率的に取得しています。sl[-1] で最大値を \(O(\log N)\) で参照できます。

• 尺取り法の正当性: 果物を売値でソートしているため、ウィンドウ \([l, r]\) に含まれる全果物は売値の差が \(D\) 以下です。右端を固定したとき、左端を可能な限り左にすることでウィンドウを最大化し、選べる候補を増やしています。

• 答えが負になるケース: 全果物の利益が負の場合でも、少なくとも1個選ぶ必要があるため、初期値を -inf にして最大利益（最も損失が小さいもの）を正しく捕捉しています。

  ソースコード

import sys
from sortedcontainers import SortedList

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    D = int(input_data[idx]); idx += 1
    
    fruits = []
    for i in range(N):
        C = int(input_data[idx]); idx += 1
        P = int(input_data[idx]); idx += 1
        fruits.append((P, P - C))
    
    # Sort by P (selling price)
    fruits.sort(key=lambda x: x[0])
    
    # Sliding window: for each window [l, r] where fruits[r].P - fruits[l].P <= D,
    # we want to maximize the sum of positive profits + (if all profits are negative, 
    # we must pick the maximum single profit).
    #
    # Strategy: Use a sliding window on sorted P values.
    # For each right endpoint r, find the smallest l such that P[r] - P[l] <= D.
    # Within this window, we want to pick all fruits with positive profit (P_i - C_i > 0)
    # and sum them up. If no fruit has positive profit, pick the one with maximum profit.
    #
    # We need to efficiently track:
    # 1. Sum of positive profits in the window
    # 2. Count of positive profits in the window
    # 3. Maximum profit in the window (for the case all are negative)
    #
    # Actually, the answer for a window is:
    # - If there are positive profit items: sum of positive profits
    # - Else: max profit (which is negative or zero)
    #
    # But we also need to consider: even if there are positive profit items, 
    # we must select at least 1, which is already satisfied by selecting positive ones.
    #
    # We want the maximum over all valid windows.
    
    # We can use a sliding window approach with a multiset to track max profit
    # and maintain sum of positive profits.
    
    ans = -float('inf')
    l = 0
    sum_positive = 0
    count_positive = 0
    # Use a SortedList to get maximum profit in window efficiently
    sl = SortedList()
    
    for r in range(N):
        p, profit = fruits[r]
        if profit > 0:
            sum_positive += profit
            count_positive += 1
        sl.add(profit)
        
        # Shrink window from left if price difference exceeds D
        while fruits[r][0] - fruits[l][0] > D:
            p_l, profit_l = fruits[l]
            if profit_l > 0:
                sum_positive -= profit_l
                count_positive -= 1
            sl.remove(profit_l)
            l += 1
        
        # Calculate best for this window
        if count_positive > 0:
            candidate = sum_positive
        else:
            # All profits <= 0, must pick the maximum one
            candidate = sl[-1]
        
        if candidate > ans:
            ans = candidate
    
    print(ans)

main()

---

この解説は claude4.6opus-thinking によって生成されました。