概要

一列に並んだ \(N\) 個の地点から連続する区間 \([l, r]\) を選び、隣接地点間の標高差の絶対値の合計（総高低差）が \(K\) 以上となる区間のうち、含まれる地点数が最小のものを求める問題です。

考察

重要な気づき：累積和の利用

隣接する地点間の標高差の絶対値を \(D_i = |A_{i+1} - A_i|\)（\(i = 0, 1, \ldots, N-2\)、0-indexed）と定義します。すると、区間 \([l, r]\)（1-indexed）の総高低差は：

\[\sum_{i=l}^{r-1} |A_{i+1} - A_i| = \sum_{i=l-1}^{r-2} D_i\]

これは \(D\) の連続部分和です。\(D\) の累積和 \(S\) を定義すると：

\[S_0 = 0, \quad S_j = D_0 + D_1 + \cdots + D_{j-1}\]

区間の総高低差は \(S_{r-1} - S_{l-1}\) と表せます。

変数の置き換え

\(a = l - 1\)、\(b = r - 1\) と置くと、\(0 \leq a \leq b \leq N - 1\) で： - 総高低差 \(= S_b - S_a\) - 地点数 \(= b - a + 1\)

目標: \(S_b - S_a \geq K\) を満たす \((a, b)\) の中で \(b - a + 1\) を最小化する。

素朴なアプローチの問題点

全ての \((a, b)\) の組を試すと \(O(N^2)\) で、\(N \leq 2 \times 10^5\) では TLE になります。

高速化のポイント

\(D_i \geq 0\) なので \(S\) は単調非減少です。この性質がカギです。

各 \(b\) に対して、\(S_a \leq S_b - K\) を満たす最大の \(a\)（\(\leq b\)）を見つければ、\(b - a + 1\) が最小になります。\(S\) が単調非減少なので、条件 \(S_a \leq S_b - K\) を満たす \(a\) の範囲は \([0, \text{ある値}]\) の区間になり、二分探索で最大の \(a\) を \(O(\log N)\) で見つけられます。

具体例

\(A = [1, 5, 3, 8]\), \(K = 5\) の場合： - \(D = [4, 2, 5]\), \(S = [0, 4, 6, 11]\) - \(b = 3\) のとき \(S_3 - K = 6\)。\(S_a \leq 6\) を満たす最大の \(a\) は \(2\)（\(S_2 = 6\)）。地点数 \(= 3 - 2 + 1 = 2\)。 - これは地点 3→4（標高 \(3 \to 8\)、高低差 \(5 \geq K\)）に対応します。

アルゴリズム

1. 隣接標高差の配列 \(D\) を計算する。
2. \(D\) の累積和 \(S\) を計算する。
3. 全区間の総高低差 \(S_{N-1}\) が \(K\) 未満なら \(-1\) を出力して終了。
4. 各 \(b = 0, 1, \ldots, N-1\) に対して：
   • \(\text{target} = S_b - K\) を計算。\(\text{target} < 0\) ならスキップ。
   • \(S[0], S[1], \ldots, S[b]\) の中で \(S_a \leq \text{target}\) を満たす最大の \(a\) を二分探索（bisect_right）で求める。
   • 見つかれば \(b - a + 1\) で答えを更新。
5. 答えの最小値を出力。

計算量

• 時間計算量: \(O(N \log N)\)（各 \(b\) について二分探索を行うため）
• 空間計算量: \(O(N)\)（累積和配列の分）

実装のポイント

• \(D_i \geq 0\) より \(S\) が単調非減少であることが二分探索の前提条件。この性質がなければ二分探索は使えません。

• bisect_right(S, target, 0, b+1) - 1 で「\(S_a \leq \text{target}\) を満たす最大の \(a\)」を求めています。bisect_right は target より大きい最初の位置を返すので、そこから \(1\) 引くと \(\leq \text{target}\) の最大インデックスが得られます。

• \(K\) が最大 \(10^{18}\) と非常に大きいため、条件を満たすルートが存在しない場合（全区間の総高低差が \(K\) 未満）の判定を忘れずに行いましょう。

  ソースコード

import sys
from collections import deque

def solve():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i+2]) for i in range(N)]
    
    if N <= 1:
        if K <= 0:
            print(1)
        else:
            print(-1)
        return
    
    # D[i] = |A[i+1] - A[i]| for i = 0..N-2
    D = [abs(A[i+1] - A[i]) for i in range(N-1)]
    
    # prefix sum of D
    # S[0] = 0, S[i] = D[0] + D[1] + ... + D[i-1]
    S = [0] * N
    for i in range(N-1):
        S[i+1] = S[i] + D[i]
    
    total = S[N-1]
    if total < K:
        print(-1)
        return
    
    # We want the minimum (r - l + 1) such that S[r] - S[l] >= K
    # where 0 <= l < r <= N-1 (using S indices, route is from point l+1 to point r+1... 
    # Let me re-think the indexing.
    
    # Route (l, r) with 1-indexed points, 1 <= l <= r <= N
    # Total elevation = sum_{i=l}^{r-1} |A[i+1]-A[i]| = S[r-1] - S[l-1] (using 0-indexed S where S has N elements)
    # Wait, let me redefine clearly.
    
    # Let P[j] = sum of D[0..j-1] for j=0..N-1, so P[0]=0, P[j] = |A[1]-A[0]| + ... + |A[j]-A[j-1]|
    # This is exactly S as defined above. S[j] = sum_{i=0}^{j-1} D[i]
    
    # Route from point l to point r (1-indexed): elevation = sum_{i=l}^{r-1} |A[i+1]-A[i]|
    # In 0-indexed D: = sum_{i=l-1}^{r-2} D[i] = S[r-1] - S[l-1]
    # Number of points = r - l + 1
    
    # Let's substitute: let a = l-1, b = r-1, so 0 <= a <= b <= N-1
    # Elevation = S[b] - S[a], points = b - a + 1
    # We want S[b] - S[a] >= K, minimize b - a + 1.
    
    # This is equivalent to: for each b, find the largest a <= b such that S[b] - S[a] >= K,
    # i.e., S[a] <= S[b] - K. We want to maximize a (to minimize b - a + 1).
    
    # Since S is non-decreasing (D[i] >= 0), we can binary search for each b.
    # For each b, find the largest a <= b such that S[a] <= S[b] - K.
    # Since S is non-decreasing, S[a] <= S[b] - K means a <= (some threshold).
    # The largest such a is found by binary searching for S[b] - K in S[0..b].
    
    import bisect
    
    ans = N + 1
    for b in range(N):
        target = S[b] - K
        if target < 0:
            continue
        # Find largest a in [0, b] with S[a] <= target
        # Since S is non-decreasing, use bisect_right to find insertion point of target
        # then the largest index with S[a] <= target is bisect_right(..., target) - 1
        idx = bisect.bisect_right(S, target, 0, b + 1) - 1
        if idx >= 0:
            a = idx
            length = b - a + 1
            ans = min(ans, length)
    
    if ans > N:
        print(-1)
    else:
        print(ans)

solve()

---

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