概要

この問題は、果物の売値の最大値と最小値の差が \(D\) 以下という制約のもとで、選んだ果物の利益（売値 \(-\) 仕入れ値）の合計を最大化する問題です。

売値でソートを行うことで、選ぶ果物の「最小の売値」と「最大の売値」を固定したときの最適解を、累積和とスライディングウィンドウ（単調キュー）を用いて \(O(N \log N)\) で効率的に求めることができます。

---

考察

1. 売値でのソートと区間の決定

「売値の最大値と最小値の差が \(D\) 以下」という条件を扱いやすくするため、まずは果物を売値 \(P_i\) の昇順にソートします。

ソート後、選んだ果物のうち、最も売値が小さい（インデックスが最小の）果物を \(L\)、最も売値が大きい（インデックスが最大の）果物を \(R\) とします（\(L \le R\)）。 このとき、条件を満たすためには \(P_R - P_L \le D\) である必要があります。

2. 間にある果物の選び方

\(L\) と \(R\) を選んだとき、その間にある果物 \(i\)（\(L < i < R\)）は、選んでも選ばなくても「最大値と最小値の差」に影響を与えません（なぜなら、ソート済みなので \(P_L \le P_i \le P_R\) が保証されるためです）。 したがって、利益を最大化するためには、間にある果物のうち利益 \(V_i = P_i - C_i\) が正のものをすべて選ぶのが最適です。

よって、選ぶ果物が 1 個（\(L = R\)）の場合と、2 個以上（\(L < R\)）の場合に分けて考えます。

• 1 個だけ選ぶ場合 (\(L = R\)): 利益は \(V_L\) となります。
• 2 個以上選ぶ場合 (\(L < R\)): 利益は以下のように表せます。 $\( \text{利益} = V_L + V_R + \sum_{i=L+1}^{R-1} \max(0, V_i) \)$

3. 式の変形による高速化

2 個以上選ぶ場合の利益の式を、高速に計算できる形に変形します。 正の利益の累積和を \(S_k = \sum_{i=1}^k \max(0, V_i)\) と定義します（\(S_0 = 0\)）。これを用いると、中間の和は \(S_{R-1} - S_L\) と表せます。

\[ \begin{aligned} \text{利益} &= V_L + V_R + S_{R-1} - S_L \\ &= (V_L - S_L) + (V_R + S_{R-1}) \end{aligned} \]

ここで、\(\max(0, V_x) = V_x - \min(0, V_x)\) という関係式を利用して、さらに整理します。 - \(V_L - S_L = V_L - (S_{L-1} + \max(0, V_L)) = \min(0, V_L) - S_{L-1}\) - \(V_R + S_{R-1} = V_R + (S_R - \max(0, V_R)) = \min(0, V_R) + S_R\)

これらを代入すると、利益の式は以下のように \(L\) の項と \(R\) の項に完全に分離できます。 $\( \text{利益} = \left( \min(0, V_L) - S_{L-1} \right) + \min(0, V_R) + S_R \)$

ここで、\(A_i = \min(0, V_i) - S_{i-1}\) と定義すると、利益は次のようにシンプルになります。 $\( \text{利益} = A_L + \min(0, V_R) + S_R \)$

4. スライディングウィンドウの適用

\(R\) を固定したとき、満たすべき条件は以下の通りです。 - \(1 \le L < R\) - \(P_R - P_L \le D\)

この条件を満たす範囲内で \(A_L\) を最大化すれば、その \(R\) に対する最大利益が求まります。 \(R\) を右に動かすにつれて、条件を満たす \(L\) の下限（\(L_{\min}\)）も右に動いていきます。これは典型的なスライディングウィンドウ最大値問題であり、双方向キュー（std::deque）を用いることで、すべての \(R\) に対する最適な \(L\) を線形時間で求めることができます。

---

アルゴリズム

1. 前処理:
   • 果物を売値 \(P_i\) の昇順にソートします。
   • 各果物の利益 \(V_i = P_i - C_i\) を計算します。
   • 正の利益の累積和 \(S_i\) を計算します。
   • 各 \(i\) について \(A_i = \min(0, V_i) - S_{i-1}\) を計算します。
2. 初期化:
   • 答えの初期値を「1個だけ選ぶ場合」の最大値（\(\max_{1 \le i \le N} V_i\)）とします。
3. スライディングウィンドウ:
   • \(R\) を \(2\) から \(N\) までループします。
   • 新たに選択可能になった \(L = R-1\) を deque に追加します。この際、単調性を維持するために \(A_{R-1}\) 以下の要素を deque の末尾から取り除きます。
   • \(P_R - P_{L_{\min}} > D\) となる間、\(L_{\min}\) を右に進めます。
   • deque の先頭にあるインデックスが \(L_{\min}\) 未満であれば、ウィンドウ外となったため取り除きます。
   • deque の先頭にあるインデックスを \(L\) とし、そのときの利益 \(A_L + \min(0, V_R) + S_R\) で答えを更新します。

---

計算量

• 時間計算量: \(O(N \log N)\)

  • 果物のソートに \(O(N \log N)\) かかります。
  • スライディングウィンドウの遷移において、各インデックスは deque に高々1回追加され、高々1回削除されるため、この部分は \(O(N)\) です。
  • したがって、全体のボトルネックはソートとなり、全体で \(O(N \log N)\) となります。

• 空間計算量: \(O(N)\)

  • 果物の情報、累積和、および deque の保持に \(O(N)\) のメモリを使用します。

---

実装のポイント

• 1個だけ選ぶ場合の考慮: すべての果物の利益が負である場合など、複数個選ぶよりも1個だけ選ぶ方が利益が大きくなることがあります。そのため、答えの初期値は必ず「1個だけ選ぶ場合の最大値」で初期化する必要があります。

• 型への配慮: 利益の合計や累積和は非常に大きな値（または小さな負の値）になり得るため、C++では long long 型を使用し、初期値の「マイナス無限大」も十分に小さな値（-4e18 など）に設定します。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

struct Fruit {
    long long C, P, V;
    bool operator<(const Fruit& other) const {
        return P < other.P;
    }
};

int main() {
    // Optimize standard I/O operations for speed
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long D;
    if (!(cin >> N >> D)) return 0;

    vector<Fruit> fruits(N);
    for (int i = 0; i < N; ++i) {
        cin >> fruits[i].C >> fruits[i].P;
        fruits[i].V = fruits[i].P - fruits[i].C;
    }

    // Sort fruits by selling price P
    sort(fruits.begin(), fruits.end());

    vector<long long> V(N + 1), P(N + 1);
    for (int i = 1; i <= N; ++i) {
        V[i] = fruits[i - 1].V;
        P[i] = fruits[i - 1].P;
    }

    vector<long long> V_plus(N + 1);
    for (int i = 1; i <= N; ++i) {
        V_plus[i] = max(0LL, V[i]);
    }

    // Prefix sums of positive profits
    vector<long long> S(N + 1, 0);
    for (int i = 1; i <= N; ++i) {
        S[i] = S[i - 1] + V_plus[i];
    }

    // Auxiliary array for RMQ
    vector<long long> A(N + 1);
    for (int i = 1; i <= N; ++i) {
        A[i] = min(0LL, V[i]) - S[i - 1];
    }

    // Base case: choosing exactly 1 fruit
    long long ans = -4e18; // Negative infinity
    for (int i = 1; i <= N; ++i) {
        ans = max(ans, V[i]);
    }

    // Sliding window maximum using deque
    deque<int> dq;
    int L_min = 1;
    for (int R = 2; R <= N; ++R) {
        int new_L = R - 1;
        while (!dq.empty() && A[dq.back()] <= A[new_L]) {
            dq.pop_back();
        }
        dq.push_back(new_L);

        // Maintain the condition P[R] - P[L_min] <= D
        while (P[R] - P[L_min] > D) {
            L_min++;
        }

        // Remove elements out of the current window [L_min, R-1]
        while (!dq.empty() && dq.front() < L_min) {
            dq.pop_front();
        }

        if (!dq.empty()) {
            long long max_A = A[dq.front()];
            long long current_val = max_A + min(0LL, V[R]) + S[R];
            ans = max(ans, current_val);
        }
    }

    cout << ans << "\n";

    return 0;
}

---

この解説は gemini-3.5-flash-thinking によって生成されました。