概要

隣り合う地点の標高差の絶対値の合計（総高低差）が \(K\) 以上になる区間 \((l,r)\) のうち、含まれる地点数 \(r-l+1\) を最小化します。

考察

重要な気づき

ルート \((l,r)\) の総高低差は $\(\sum_{i=l}^{r-1} |A_{i+1}-A_i|\)\( であり、これは「隣接差分」配列 \)\(B_i = |A_{i+1}-A_i|\quad (1 \le i \le N-1)\)\( の区間和 \)\(\sum_{i=l}^{r-1} B_i\)$ そのものです。

つまり問題は、

• 長さ \(N-1\) の非負配列 \(B\) がある
• 区間和が \(K\) 以上となる 最短の連続部分列の長さ を求める

に言い換えられます。求まった最短長を \(m\)（これは辺の本数）とすると、地点数は辺より 1 つ多いので答えは \(m+1\) です。

素朴解がダメな理由

全ての \((l,r)\) を試すと区間は \(O(N^2)\) 個あり、各区間の総高低差を愚直に計算すると当然間に合いません（\(N \le 2\times 10^5\)）。

累積和で区間和を \(O(1)\) にしても、全区間列挙自体が \(O(N^2)\) なので TLE になります。

どう解決するか

\(B_i \ge 0\)（絶対値なので必ず非負）であることが決定的です。
非負配列の「区間和がある値以上になる最短区間」は、しゃくとり法（two pointers / sliding window）で \(O(N)\) で求められます。

アルゴリズム

1. \(B[i] = |A[i+1]-A[i]|\)（\(i=0..N-2\)）を作る。
2. しゃくとり法で、区間 \([left, right]\)（\(B\) 上の区間）の和 \(s\) を管理する。
   • right を 0 から順に伸ばして \(s\) に加える。
   • \(s \ge K\) になったら、条件を満たしているのでその長さ right-left+1 を答え候補にしつつ、 さらに短くできないか left を進めて（\(s\) から引いて）縮める。
3. 最短の辺の本数が ans として得られる。地点数は ans + 1。
4. 一度も \(s \ge K\) にならなければ不可能なので -1。

（例） \(A = [1, 4, 2, 7]\) のとき
\(B = [|4-1|, |2-4|, |7-2|] = [3,2,5]\)。
\(K=6\) なら、区間 \([2,3]\)（\(2+5=7\)）が最短で長さ 2（辺 2 本）→ 地点数は 3。

計算量

• 時間計算量: \(O(N)\)（left も right も高々 \(N\) 回ずつ進む）
• 空間計算量: \(O(N)\)（差分配列 \(B\) を保持）

実装のポイント

• 答えは「辺の本数」ではなく「地点数」なので、最後に +1 する点に注意。

• \(K\) は最大 \(10^{18}\) なので、和 s は 64bit 整数相当で扱う（Python なら自動でOK）。

• \(N=1\) のときはそもそも辺がなく総高低差は常に 0 なので、\(K \ge 1\) の制約下では必ず -1。

  ソースコード

import sys

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

    if N <= 1:
        print(-1)
        return

    B = [abs(A[i+1] - A[i]) for i in range(N - 1)]

    left = 0
    s = 0
    ans = 10**30
    for right, v in enumerate(B):
        s += v
        while s >= K:
            ans = min(ans, right - left + 1)
            s -= B[left]
            left += 1

    if ans == 10**30:
        print(-1)
    else:
        print(ans + 1)

if __name__ == "__main__":
    main()

---

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