概要

山の標高列から、狭義単調増加のあと狭義単調減少する「山型」の連続区間のうち、最大値と最小値の差が \(K\) 以上であるものの最大長を求めます。

ポイントは、標高差の符号列を見て、山型になり得る最大区間を一度の走査で区切ることです。

考察

区間 \([l, r]\) が山型であるとは、隣り合う標高の増減が

• 最初は増加
• ある地点から減少
• ただし増加のみ、減少のみも可

となっていることです。

つまり、隣接する差の符号を見たとき、

• \(+\) が続いたあとに \(-\) が続く形は OK
• \(-\) のあとに \(+\) が出てくると NG
• \(0\)、つまり等しい標高があると NG

です。

例えば、標高列が

\[ 1, 3, 5, 4, 2 \]

なら、差の符号は

\[ +, +, -, - \]

なので山型です。

一方で、

\[ 5, 3, 2, 4 \]

は差の符号が

\[ -, -, + \]

となり、減少したあとに増加しているため山型ではありません。

---

素朴にすべての区間 \([l, r]\) を調べると、区間数は \(O(N^2)\) 個あります。
\(N \leq 10^6\) なので、これは到底間に合いません。

そこで、山型であり続ける最大の連続区間を左から順に作ります。

重要な観察は次の通りです。

ある区間全体が山型で、かつ最大値と最小値の差が \(K\) 以上なら、その区間全体が答えの候補になります。

また、その区間の中の一部だけを選んでも長さは短くなるだけです。
したがって、山型であり続ける最大区間ごとに、

\[ \max - \min \geq K \]

を満たすかだけを確認すれば十分です。

---

山型が壊れるのは次の 2 パターンです。

1. 隣接する標高が等しい場合

山型の定義は狭義不等号なので、

\[ H_i = H_{i+1} \]

を含む区間は山型になりません。

そのため、ここで区間を完全に切ります。

2. 減少のあとに増加する場合

差の符号が

\[ - \to + \]

となる場所は谷です。

例えば、

\[ 5, 3, 4 \]

は

\[ 5 > 3 < 4 \]

なので山型ではありません。

この場合、前の山型区間は谷の位置までで終了します。
ただし、谷の位置から次の増加列を始めることはできるので、新しい区間は谷の位置から開始します。

アルゴリズム

左から順に標高列を走査します。

現在見ている山型区間について、次を管理します。

• start: 現在の山型区間の開始位置
• seg_min: 現在の区間内の最小標高
• seg_max: 現在の区間内の最大標高
• prev_sign: 直前の差の符号
  • 増加なら \(+1\)
  • 減少なら \(-1\)
  • まだ差がないなら \(0\)

隣り合う標高 \(a = H_i\), \(b = H_{i+1}\) を見て、現在の差の符号 curr を求めます。

curr == 0 の場合

標高が等しいので、山型区間はここで途切れます。

現在の区間について、

\[ seg\_max - seg\_min \geq K \]

なら答えを更新します。

その後、新しい区間を \(H_{i+1}\) から始めます。

prev_sign == -1 and curr == 1 の場合

減少のあとに増加しているので、谷ができています。

このままでは山型ではないため、現在の区間を谷の位置で終了させます。

現在の区間を評価したあと、新しい区間を谷の位置から始めます。

それ以外の場合

現在の山型区間をそのまま伸ばせます。

seg_min, seg_max を更新し、次へ進みます。

最後に、走査終了後の区間も忘れずに評価します。

計算量

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

入力配列を除けば、走査中に持つ変数は定数個だけです。

実装のポイント

• 隣接する標高が等しい場合は、その 2 点を同じ山型区間に含められないため、区間を完全に分けます。

• 減少から増加に変わる場合は、谷の点を新しい区間の開始点にします。

  • 例: \(5, 3, 4\)
  • 前の区間は \(5, 3\)
  • 次の区間は \(3, 4\)

• \(N = 1\) の場合、区間の最大値と最小値の差は \(0\) です。制約上 \(K \geq 1\) なので、答えは必ず \(0\) です。

• 最後の区間はループ内で確定しないため、ループ後に必ず評価します。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N = data[0]
    K = data[1]

    if N <= 1:
        print(0)
        return

    h_prev = data[2]
    start = 0
    seg_min = h_prev
    seg_max = h_prev
    prev_sign = 0
    ans = 0

    idx = 3
    for i in range(N - 1):
        b = data[idx]
        idx += 1
        a = h_prev

        if b > a:
            curr = 1
        elif b < a:
            curr = -1
        else:
            curr = 0

        if curr == 0:
            if seg_max - seg_min >= K:
                length = i - start + 1
                if length > ans:
                    ans = length
            start = i + 1
            seg_min = b
            seg_max = b
            prev_sign = 0
            h_prev = b
            continue

        if prev_sign == -1 and curr == 1:
            if seg_max - seg_min >= K:
                length = i - start + 1
                if length > ans:
                    ans = length
            start = i
            seg_min = a
            seg_max = a

        if b < seg_min:
            seg_min = b
        elif b > seg_max:
            seg_max = b

        prev_sign = curr
        h_prev = b

    if seg_max - seg_min >= K:
        length = N - start
        if length > ans:
            ans = length

    print(ans)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.5-high によって生成されました。