概要

各峰を「山型の頂点」とみなしたとき、その頂点を中心に左へは狭義単調増加、右へは狭義単調減少が続く最長の区間を求め、その中で標高差が \(K\) 以上になるものの最大の峰数を答える問題です。

考察

まず素朴に考えると、すべての区間 \([l, r]\) を試して「山型かどうか」「標高差が \(K\) 以上か」を判定する方法がありますが、区間は \(O(N^2)\) 個あり、\(N \leq 10^6\) では到底間に合いません。

ここで重要な観察をします。山型の区間は必ず「頂点」となる峰 \(k\) を 1 つ持ちます。そこで 頂点を固定して考える ことにします。

頂点 \(k\) を固定したとき、

• 頂点から左側は \(H_l < H_{l+1} < \cdots < H_k\) となるよう、狭義単調増加が続く限り左へ伸ばせます。
• 頂点から右側は \(H_k > H_{k+1} > \cdots > H_r\) となるよう、狭義単調減少が続く限り右へ伸ばせます。

このとき得られる「頂点 \(k\) を中心とする最大の山型区間」が、頂点 \(k\) に対する最良候補になります。理由は次の通りです。

頂点 \(k\) を含む山型区間では、

• 最大値は常に \(H_k\)（頂点）です。
• 最小値は両端 \(H_l, H_r\) のうち小さい方です（左は増加・右は減少なので両端が最も低い）。

区間を最大まで伸ばすと両端の標高は下がる（または変わらない）ため、標高差 \(H_k - \min(H_l, H_r)\) は最大化されます。さらに区間の長さも最大になります。つまり「最大まで伸ばした区間で標高差が \(K\) 未満なら、それより短い区間でも条件を満たさない」ことが言えるので、各頂点について最大の山型区間だけを調べれば十分です。

アルゴリズム

連続部分列の長さを前計算する典型テクニックを使います。

• \(\text{up}[i]\)：峰 \(i\) で終わる狭義単調増加列の長さ
  • \(H_{i-1} < H_i\) なら \(\text{up}[i] = \text{up}[i-1] + 1\)、そうでなければ \(1\)
• \(\text{down}[i]\)：峰 \(i\) から始まる狭義単調減少列の長さ
  • \(H_i > H_{i+1}\) なら \(\text{down}[i] = \text{down}[i+1] + 1\)、そうでなければ \(1\)

これらを使うと、峰 \(i\) を頂点とする最大の山型区間は

• 左端 \(l = i - \text{up}[i] + 1\)
• 右端 \(r = i + \text{down}[i] - 1\)
• 長さ \(\text{up}[i] + \text{down}[i] - 1\)（頂点を二重に数えるので \(-1\)）

と表せます。

各 \(i\) について、最大値 \(H_i\) と最小値 \(\min(H_l, H_r)\) の差が \(K\) 以上であれば、その長さを答えの候補として更新します。

具体例：\(H = [1, 3, 5, 2, 4]\), \(K = 3\) を考えます。

• \(i=2\)（値 \(5\)）が頂点のとき、左へ \(1, 3, 5\)（増加）、右へ \(5, 2\)（減少）と伸びるので区間は \([1,3,5,2]\)、長さ \(4\)。最大値 \(5\)、両端は \(1\) と \(2\) なので最小値 \(1\)、差は \(4 \geq 3\) で条件を満たします。

このように各頂点を \(O(1)\) で評価できます。

計算量

• 時間計算量: \(O(N)\)（前計算も走査も線形）
• 空間計算量: \(O(N)\)（配列 \(H, \text{up}, \text{down}\)）

実装のポイント

• 山型の定義は 狭義 の不等号です。\(H_i = H_{i+1}\) の箇所では増加列・減少列が途切れる（長さ \(1\) にリセットされる）ことに注意してください。等号で繋いでしまうと WA になります。

• 区間内の最小値は、両端の値のうち小さい方を取れば十分です（頂点に向かって増加・減少するため、両端が最も低い）。わざわざ区間全体の最小値を計算する必要はありません。

• \(N \leq 10^6\) と大きいため、入力は sys.stdin.buffer.read() でまとめて読み込むと高速です。

• 長さ \(1\) の区間（峰 1 つ）も山型ですが、その場合は標高差 \(0\) なので \(K \geq 1\) の制約上、条件を満たすことはありません。撮影候補が存在しないときは初期値の \(0\) がそのまま出力されます。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0]); k = int(data[1])
    H = [int(x) for x in data[2:2+n]]

    up = [1] * n
    for i in range(1, n):
        if H[i-1] < H[i]:
            up[i] = up[i-1] + 1

    down = [1] * n
    for i in range(n-2, -1, -1):
        if H[i] > H[i+1]:
            down[i] = down[i+1] + 1

    ans = 0
    for i in range(n):
        l = i - up[i] + 1
        r = i + down[i] - 1
        hl = H[l]
        hr = H[r]
        mn = hl if hl < hr else hr
        if H[i] - mn >= k:
            length = up[i] + down[i] - 1
            if length > ans:
                ans = length

    print(ans)

main()

---

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