概要

東西に並んだ山の峰の中から、「山型（左側が狭義単調増加・右側が狭義単調減少）」かつ「標高の最大値と最小値の差が \(K\) 以上」となる連続区間のうち、最も長いものの長さを求める問題です。

考察

山型区間の「頂上」に注目する

山型区間 \([l, r]\) には必ず最高点となる頂上 \(k\) が存在し、

\[H_l < \cdots < H_k > \cdots > H_r\]

という形になります。そこで「頂上を \(k\) に固定したとき、最も長くなる山型区間はどこか？」を考えます。

頂上 \(k\) から左へは「狭義単調増加が続く限り」、右へは「狭義単調減少が続く限り」伸ばすのが、頂上 \(k\) を持つ山型区間として最長です。 - 左端：\(H_{i} > H_{i-1}\) が成り立つ限り左へ伸ばせる - 右端：\(H_{i} > H_{i+1}\) が成り立つ限り右へ伸ばせる

これを各 \(k\) についてあらかじめ求めておけば、頂上ごとの最長山型区間が一発でわかります。

標高差の条件を考える

頂上 \(k\) を固定した最長区間 \([L, R]\) について、 - 最大値は必ず頂上 \(H_k\) - 最小値は両端のうち低い方 \(\min(H_L, H_R)\)（増加・減少の端が最も低いため）

となります。よって標高差は \(H_k - \min(H_L, H_R)\) です。

部分区間を考えなくてよい理由

「最長区間では条件を満たさないが、もっと短い区間なら満たす」ことはあるでしょうか？ 区間を縮めると最大値は変わらず（頂上は残る）、最小値は上がる方向にしか動かないため、標高差は縮める方向にしか変化しません。 つまり、頂上 \(k\) について最長区間で条件を満たさなければ、どの部分区間でも満たせません。さらに長さも最長区間が一番長いので、各頂上は最長区間だけ調べれば十分です。

素朴な方法との比較

全区間 \(O(N^2)\) を調べると \(N \leq 10^6\) では間に合いません。上の観察により、各頂上 \(k\) について \(O(1)\) で判定できるので、全体で \(O(N)\) に落とせます。

アルゴリズム

1. 左方向の増加範囲を前計算：incLeft[i] を「\(i\) を右端として狭義単調増加が続く左端の位置」とする。
   • \(H_i > H_{i-1}\) なら incLeft[i] = incLeft[i-1]、そうでなければ incLeft[i] = i。
2. 右方向の減少範囲を前計算：decRight[i] を「\(i\) を左端として狭義単調減少が続く右端の位置」とする。
   • \(H_i > H_{i+1}\) なら decRight[i] = decRight[i+1]、そうでなければ decRight[i] = i。
3. 各頂上 \(k\) を全探索：
   • \(L = \) incLeft[k]、\(R = \) decRight[k] とすると、\([L, R]\) が頂上 \(k\) の最長山型区間。
   • \(H_k - \min(H_L, H_R) \geq K\) なら、長さ \(R - L + 1\) で答えを更新。

具体例

\(H = [1, 3, 5, 2, 4]\)、\(K = 3\) のとき、頂上 \(k=2\)（標高 \(5\)）に注目すると、 - 左へは \(1 < 3 < 5\) と伸びて \(L = 0\) - 右へは \(5 > 2\) で止まり \(R = 3\)（次は \(2 < 4\) なので伸びない）

区間 \([0,3] = (1,3,5,2)\) は山型で、最大 \(5\)・最小 \(1\)、差 \(4 \geq 3\) を満たすので長さ \(4\) が候補になります。

計算量

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

実装のポイント

• 標高差 \(H_k - \min(H_L, H_R)\) の計算で、最小値は 両端だけ を見れば十分（山型なので内部の点はすべて両端以上）。

• \(N\) が最大 \(10^6\) と大きいため、入力は scanf などの高速な方法を使うとよい。

• 区間の長さや標高差は最大で \(10^9\) を超えうるので、long long を用いてオーバーフローを防ぐ。

• 頂上 1 つだけ（長さ 1）の区間は標高差 \(0\) となり、\(K \geq 1\) の制約から条件を満たさないため、撮影候補がなければ自然と答えは \(0\) になる。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N; long long K;
    {
        // fast input
    }
    scanf("%d %lld", &N, &K);
    vector<long long> H(N);
    for(int i=0;i<N;i++) scanf("%lld", &H[i]);
    
    vector<int> incLeft(N), decRight(N);
    for(int i=0;i<N;i++){
        if(i>0 && H[i]>H[i-1]) incLeft[i]=incLeft[i-1];
        else incLeft[i]=i;
    }
    for(int i=N-1;i>=0;i--){
        if(i<N-1 && H[i]>H[i+1]) decRight[i]=decRight[i+1];
        else decRight[i]=i;
    }
    
    long long ans=0;
    for(int k=0;k<N;k++){
        int L=incLeft[k];
        int R=decRight[k];
        long long mn = min(H[L], H[R]);
        if(H[k]-mn >= K){
            long long len = (long long)R - L + 1;
            if(len>ans) ans=len;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

---

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