概要

東西に並んだ \(N\) 個の山から、山型（単調増加した後に単調減少する形状）であり、かつ「最大標高と最小標高の差が \(K\) 以上」という条件を満たす連続する区間のうち、最大の長さを求める問題です。

考察

1. 素朴なアプローチとその限界

すべての区間 \([l, r]\)（\(1 \le l \le r \le N\)）を全探索することを考えます。 区間の選び方は \(O(N^2)\) 通りあり、それぞれの区間が「山型か」「最大値と最小値の差が \(K\) 以上か」を判定するのに \(O(N)\) かかるため、全体で \(O(N^3)\)（工夫しても \(O(N^2)\)）の計算量になります。 本問題の制約は \(N \le 10^6\) であるため、このアプローチでは実行時間制限（TLE）になってしまいます。

2. 「山頂」を固定するアプローチ

山型区間には、必ず標高が最大となる「山頂」が存在します。 そこで、各位置 \(i\) を山頂（標高が最大となる位置）としたときに、左右にどこまで区間を広げられるかを考えます。

位置 \(i\) を山頂とする最大の山型区間を \([L[i], R[i]]\) とします。 * 左方向（単調増加部分）: \(i\) から左に向かって、標高が下がり続ける（左に行くほど低くなる）限界のインデックスを \(L[i]\) とします。すなわち、 \(H_{L[i]} < H_{L[i]+1} < \cdots < H_i\) が成り立ちます。 * 右方向（単調減少部分）: \(i\) から右に向かって、標高が下がり続ける（右に行くほど低くなる）限界のインデックスを \(R[i]\) とします。すなわち、 \(H_i > H_{i+1} > \cdots > H_{R[i]}\) が成り立ちます。

このように定義すると、山頂 \(i\) を含む最大の山型区間は \([L[i], R[i]]\) になります。

3. 条件「標高差が \(K\) 以上」の簡略化

区間 \([L[i], R[i]]\) において、標高の最大値と最小値はどこになるでしょうか？ * 最大値: 山頂であるため、明らかに \(H_i\) です。 * 最小値: 左端に行くほど低くなり、右端に行くほど低くなるため、区間の両端のいずれか、すなわち \(\min(H_{L[i]}, H_{R[i]})\) になります。

したがって、この区間における「最大値と最小値の差が \(K\) 以上」という条件は、以下のように書き換えることができます。

\[H_i - \min(H_{L[i]}, H_{R[i]}) \ge K\]

これは、次と同値です。

\[H_i - H_{L[i]} \ge K \quad \text{または} \quad H_i - H_{R[i]} \ge K\]

この条件を満たすとき、区間 \([L[i], R[i]]\) は撮影候補となります。その長さは \(R[i] - L[i] + 1\) です。

4. \(L[i]\) と \(R[i]\) の高速な計算（動的計画法）

各 \(i\) について \(L[i]\) と \(R[i]\) を愚直に求めると全体で \(O(N^2)\) かかりますが、隣り合う要素の関係（動的計画法のようなアプローチ）を利用することで、それぞれ \(O(N)\) で計算できます。

• \(L[i]\) の求め方（左から順に計算）:

  • \(H[i-1] < H[i]\) のとき、山頂 \(i\) から左へ伸ばす流れは \(i-1\) の流れを引き継げるため、 \(L[i] = L[i-1]\) となります。
  • そうでないとき（\(H[i-1] \ge H[i]\) のとき）、左隣の山は自分より高いため左へは伸ばせません。よって、 \(L[i] = i\) となります。

• \(R[i]\) の求め方（右から順に計算）:

  • \(H[i] > H[i+1]\) のとき、山頂 \(i\) から右へ伸ばす流れは \(i+1\) の流れを引き継げるため、 \(R[i] = R[i+1]\) となります。
  • そうでないとき（\(H[i] \le H[i+1]\) のとき）、右隣の山は自分より高いため右へは伸ばせません。よって、 \(R[i] = i\) となります。

これにより、すべての \(i\) に対する \(L[i], R[i]\) を \(O(N)\) で事前に求めることができます。

---

アルゴリズム

1. 配列 \(L\) の構築

   • \(L[0] = 0\) とします。
   • \(i = 1\) から \(N-1\) まで順に、 \(H[i-1] < H[i]\) なら \(L[i] = L[i-1]\)、そうでなければ \(L[i] = i\) とします。

2. 配列 \(R\) の構築

   • \(R[N-1] = N-1\) とします。
   • \(i = N-2\) から \(0\) まで逆順に、 \(H[i] > H[i+1]\) なら \(R[i] = R[i+1]\)、そうでなければ \(R[i] = i\) とします。

3. 最大値の更新

   • 各 \(i\)（\(0 \le i < N\)）について、条件 \(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)\) となり、 \(N = 10^6\) でも高速に実行可能です。
• 空間計算量: \(O(N)\) 入力の標高配列 \(H\)、および左右の限界インデックスを記録する配列 \(L, R\) を保持するために \(O(N)\) のメモリを使用します。

---

実装のポイント

• 1次元配列での遷移: \(L[i]\) や \(R[i]\) を求める際、1つ前（あるいは1つ後ろ）の情報のみを参照するため、シンプルなループで実装できます。

• 境界条件の注意: \(R\) を求める際は右端（\(N-1\)）から逆順にループを回す必要があります。インデックスの範囲外参照に注意してください。

• 高速な入出力: Pythonでは入力数が多いため、 sys.stdin.read を用いて一括で入力を取得することで、入出力によるオーバーヘッドを減らしています。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    K = int(data[1])
    H = [int(x) for x in data[2:]]

    L = [0] * N
    for i in range(1, N):
        if H[i - 1] < H[i]:
            L[i] = L[i - 1]
        else:
            L[i] = i

    R = [0] * N
    R[N - 1] = N - 1
    for i in range(N - 2, -1, -1):
        if H[i] > H[i + 1]:
            R[i] = R[i + 1]
        else:
            R[i] = i

    ans = 0
    for i in range(N):
        if H[i] - H[L[i]] >= K or H[i] - H[R[i]] >= K:
            length = R[i] - L[i] + 1
            if length > ans:
                ans = length

    print(ans)


if __name__ == "__main__":
    solve()

---

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