概要

この問題は、与えられた \(N\) 個の山の標高データから、「山型」であり、かつ「標高の最大値と最小値の差が \(K\) 以上」という条件を満たす連続する区間のうち、最も長いものの長さを求める問題です。

考察

1. 「山型」の性質と極大区間

区間 \([l, r]\) が山頂 \(k\)（\(l \leq k \leq r\)）を持つ山型であるとき、その区間の特徴は以下の通りです。 - 山頂 \(H_k\) が区間内の最大値となる。 - 左端から山頂までは単調増加するため、左側の最小値は左端 \(H_l\) となる。 - 山頂から右端までは単調減少するため、右側の最小値は右端 \(H_r\) となる。 - したがって、区間内の最小値は \(\min(H_l, H_r)\) となる。

ここで、ある山頂 \(i\) を固定したときに、「山頂 \(i\) を中心として、左右にどこまで山型の形状を広げられるか」 を考えます。 - 左方向：\(H_{j-1} < H_j\) が成り立つ限り、左端を広げることができます。この限界の左端を \(L[i]\) とします。 - 右方向：\(H_j > H_{j+1}\) が成り立つ限り、右端を広げることができます。この限界の右端を \(R[i]\) とします。

このとき、区間 \([L[i], R[i]]\) は山頂 \(i\) を持つ極大な山型区間になります。

2. 極大区間だけを調べれば良い理由

任意の山型区間 \([l, r]\)（山頂 \(k\)）を考えます。この区間は必ず極大区間 \([L[k], R[k]]\) に含まれます（\(L[k] \le l \le k \le r \le R[k]\)）。

極大区間 \([L[k], R[k]]\) と元の区間 \([l, r]\) を比較すると、 1. 最大値: どちらも山頂の標高 \(H_k\) で等しい。 2. 最小値: 単調性より \(H_{L[k]} \le H_l\) かつ \(H_{R[k]} \le H_r\) が成り立つため、極大区間の方が最小値が等しいか、または小さくなります。 3. 標高差: 最小値が小さくなるため、極大区間の方が標高差（最大値 - 最小値）が等しいか、または大きくなります。 4. 区間の長さ: 当然、極大区間の方が等しいか、または長くなります。

このことから、もし条件（標高差 \(\ge K\)）を満たす区間 \([l, r]\) が存在するならば、それを内包する極大区間 \([L[k], R[k]]\) も必ず条件を満たし、かつ長さもそれ以上になります。 したがって、すべての \(i\)（\(1 \le i \le N\)）について、極大区間 \([L[i], R[i]]\) だけを調べれば十分です。

3. 素朴なアプローチとの比較

すべての区間 \([l, r]\) を全探索すると、区間の選び方が \(O(N^2)\) 通りあり、それぞれの山型判定に \(O(N)\) かかるため、全体で \(O(N^3)\) または \(O(N^2)\) の計算量になります。制約の \(N \le 10^6\) では実行時間制限（TLE）になってしまいます。 しかし、上記の「極大区間のみを調べる」アプローチであれば、調べるべき区間は \(N\) 個の極大区間に絞られ、前処理を行うことで各区間の判定を \(O(1)\) で行えるため、全体で \(O(N)\) の高速な処理が可能になります。

---

アルゴリズム

動的計画法（DP）に似た手法を用いて、各要素が左・右にどこまで伸ばせるかを高速に計算します。

Step 1: 左側の限界 \(L[i]\) の計算

左から右へ（\(i = 1\) から \(N-1\) へ）順に走査します。 - もし \(H_{i-1} < H_i\) ならば、山頂 \(i\) の左側は \(i-1\) の左側からそのまま繋がっているため、\(L[i] = L[i-1]\) となります。 - そうでなければ、これ以上左に伸ばせないため、\(L[i] = i\) となります。

Step 2: 右側の限界 \(R[i]\) の計算

右から左へ（\(i = N-2\) から \(0\) へ）順に走査します。 - もし \(H_i > H_{i+1}\) ならば、山頂 \(i\) の右側は \(i+1\) の右側からそのまま繋がっているため、\(R[i] = R[i+1]\) となります。 - そうでなければ、これ以上右に伸ばせないため、\(R[i] = i\) となります。

Step 3: 最大値の更新

各 \(i\)（\(0 \le i < N\)）について、極大区間 \([L[i], R[i]]\) の標高差が \(K\) 以上であるかを判定します。 標高差は \(\max(H_i - H_{L[i]}, H_i - H_{R[i]})\) と表せるため、以下のいずれかが成り立てば条件を満たします。 - \(H_i - H_{L[i]} \ge K\) - \(H_i - H_{R[i]} \ge K\)

条件を満たす場合、その区間の長さ \(R[i] - L[i] + 1\) で答えの最大値を更新します。

---

計算量

• 時間計算量: \(O(N)\) \(L\) 配列の構築に \(O(N)\)、\(R\) 配列の構築に \(O(N)\)、最後の各 \(i\) に対する判定に \(O(N)\) かかります。全体として \(O(N)\) のループを数回行うだけなので、非常に高速に動作します。
• 空間計算量: \(O(N)\) 入力の標高を格納する配列 \(H\)、および左右の限界インデックスを格納する配列 \(L, R\) をそれぞれサイズ \(N\) で保持するため、空間計算量は \(O(N)\) となります。

---

実装のポイント

• インデックスの走査方向に注意: \(L[i]\) を求める際は、前に計算した \(L[i-1]\) の値を利用するため、左から右（昇順）にループを回します。 逆に \(R[i]\) を求める際は、後ろに計算した \(R[i+1]\) の値を利用するため、右から左（降順）にループを回します。

• 高速な入出力: \(N \le 10^6\) と入力のサイズが大きいため、C++では cin.tie(NULL) や ios_base::sync_with_stdio(false) を用いて標準入出力を高速化しておくことが重要です。

  ソースコード

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

using namespace std;

int main() {
    // 標準入出力の高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

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

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    // L[i]: iから左に向かって狭義単調増加となる最小のインデックス
    vector<int> L(N);
    L[0] = 0;
    for (int i = 1; i < N; ++i) {
        if (H[i - 1] < H[i]) {
            L[i] = L[i - 1];
        } else {
            L[i] = i;
        }
    }

    // R[i]: iから右に向かって狭義単調減少となる最大のインデックス
    vector<int> R(N);
    R[N - 1] = N - 1;
    for (int i = N - 2; i >= 0; --i) {
        if (H[i] > H[i + 1]) {
            R[i] = R[i + 1];
        } else {
            R[i] = i;
        }
    }

    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        // 頂点iを山頂とする山型の最大区間 [L[i], R[i]] において、
        // 最大値 H[i] と最小値 min(H[L[i]], H[R[i]]) の差が K 以上であるか判定
        if (H[i] - H[L[i]] >= K || H[i] - H[R[i]] >= K) {
            ans = max(ans, (long long)(R[i] - L[i] + 1));
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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