概要

連続区間の 最大値−最小値が \(D\) 以下 となる「安定した」区間のうち、長さが \(K\) 以上 のものについて、取りうる 最長の長さを求めます。

考察

区間が安定している条件は
[ \max(H_l,\dots,H_r)-\min(H_l,\dots,H_r)\le D ] です。求めたいのは、この条件を満たす区間の 最大長（ただし長さ \(\ge K\)）です。

素朴解が難しい理由

全ての \((l,r)\) を試すと区間は \(O(N^2)\) 個あり、各区間で最大・最小を求めるのにさらに時間がかかるため、\(N\le 5\times 10^5\) では到底間に合いません。

重要な気づき

• 右端 \(r\) を1日ずつ伸ばしていく「尺取り法（スライディングウィンドウ）」で考えると、条件が崩れたら左端 \(l\) を進めて復元できます。
• ただし、そのためには「現在の区間 \([l,r]\) の最大値・最小値」を高速に更新できる必要があります。
• そこで 単調キュー（monotonic queue） を使うと、各ステップで最大・最小を \(O(1)\)（償却）で管理できます。

（例）区間に新しい値を追加しても、最大候補・最小候補になり得ない値をキュー末尾から捨てることで、常に先頭が最大（または最小）になるよう保てます。

アルゴリズム

以下を 0-indexed で行います。

1. 左端 \(l=0\)、答え best=0 を用意する。
2. 右端 \(r=0,1,\dots,N-1\) を順に伸ばす（\(H_r\) を区間に追加）。
3. 区間 \([l,r]\) の最大値を管理する maxdq、最小値を管理する mindq を用意し、どちらも 添字を保持する。
   • maxdq は「対応する値 \(H\) が単調非増加（大きい→小さい）」になるように保つ
     追加する値 \(x=H_r\) より小さい末尾要素は最大になり得ないので pop する。
   • mindq は「対応する値 \(H\) が単調非減少（小さい→大きい）」になるように保つ
     追加する値 \(x\) より大きい末尾要素は最小になり得ないので pop する。
4. 追加後、安定条件が崩れている間（\(H[\text{maxdq}[0]]-H[\text{mindq}[0]]>D\)）は左端を縮める：
   • もし maxdq 先頭の添字がちょうど \(l\) なら、その要素は区間外になるので popleft。
   • mindq も同様。
   • \(l\) を \(l+1\) に進める。
5. ここまでで区間 \([l,r]\) は必ず安定なので、長さ \(r-l+1\) で best を更新する。
6. 最後に best >= K なら best、そうでなければ -1 を出力する。
   （「安定した区間の最長」は求められているが、長さが \(K\) 未満なら条件を満たす区間が存在しないため）

計算量

• 時間計算量: \(O(N)\)
  （各要素は deque に高々1回入り、高々1回出るため、全体で償却 \(O(N)\)）
• 空間計算量: \(O(N)\)
  （最悪で deque が \(N\) 個の添字を保持し得る）

実装のポイント

• deque には 値ではなく添字を入れる（左端 \(l\) が動いたときに「区間から外れたか」を判定しやすい）。

• 条件違反の解消は while で行う（1回 \(l\) を動かしただけではまだ差が \(D\) を超える場合がある）。

• 最後に best がそのまま答えではなく、best >= K のチェックが必要（存在しない場合は -1）。

  ソースコード

import sys
from collections import deque

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

    maxdq = deque()  # indices, H non-increasing
    mindq = deque()  # indices, H non-decreasing

    l = 0
    best = 0

    for r, x in enumerate(H):
        while maxdq and H[maxdq[-1]] < x:
            maxdq.pop()
        maxdq.append(r)

        while mindq and H[mindq[-1]] > x:
            mindq.pop()
        mindq.append(r)

        while H[maxdq[0]] - H[mindq[0]] > D:
            if maxdq[0] == l:
                maxdq.popleft()
            if mindq[0] == l:
                mindq.popleft()
            l += 1

        if r - l + 1 > best:
            best = r - l + 1

    print(best if best >= K else -1)

if __name__ == "__main__":
    main()

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