概要

隣接する地点間の標高差の絶対値の和（総高低差）が \(K\) 以上となるような連続する地点の区間のうち、含まれる地点の数が最も少ないものを求める問題です。

考察

まず、この問題は「隣接する地点間の標高差」を扱うため、あらかじめ各区間の標高差を計算して新しい配列を作ると見通しが良くなります。 具体的には、\(D_i = |A_{i+1} - A_i|\) という長さ \(N-1\) の配列 \(D\) を考えます。すると、この問題は「配列 \(D\) の連続する部分列のうち、要素の和が \(K\) 以上となる最短の長さを求めよ」と言い換えることができます。

すべての開始地点 \(l\) と終了地点 \(r\) の組み合わせを試す素朴なアプローチ（全探索）を考えると、組み合わせの数は約 \(N^2 / 2\) 通りになります。今回の制約では \(N \le 2 \times 10^5\) なので、計算回数が数百億回に達してしまい、実行時間制限（TLE）に引っかかってしまいます。

ここで、配列 \(D\) の要素がすべて \(0\) 以上であることに注目します。 要素がすべて \(0\) 以上であれば、区間を右に伸ばす（終了地点を右にずらす）と和は単調に増加し、区間を左から縮める（開始地点を右にずらす）と和は単調に減少します。このような性質を持つ場合、「尺取り法（Two Pointers）」という手法を使うことで、無駄な探索を省き \(O(N)\) という非常に高速な時間で答えを求めることができます。

アルゴリズム

1. コーナーケースの処理 \(N = 1\) の場合、移動することができないため総高低差は常に \(0\) です。\(K \ge 1\) であるため条件を満たすことはありません。すぐに -1 を出力します。
2. 差分配列の作成 長さ \(N-1\) の配列 \(D\) を作ります。\(D_i = |A_{i+1} - A_i|\) とします。
3. 尺取り法による探索 区間の左端を表す変数 left を \(0\)、区間の和を管理する変数 current_sum を \(0\)、最小の区間の長さを記録する変数 min_length を非常に大きい値（無限大）で初期化します。 区間の右端 right を \(0\) から \(N-2\) まで順番に動かしながら、以下の操作を行います。
   • current_sum に \(D[right]\) を足します。
   • current_sum \ge K を満たしている間、以下を繰り返します：
     • 現在の区間の長さ（right - left + 1）で min_length を小さければ更新します。
     • 条件を満たすギリギリまで区間を短くしたいので、current_sum から \(D[left]\) を引き、left を \(1\) 増やして左端を縮めます。
4. 答えの出力 すべての探索を終えた後、min_length が初期値のままであれば、条件を満たすルートが存在しなかったということなので -1 を出力します。 更新されていれば、求めたいのは「地点の数」なので、区間の長さ（差分の数）に \(1\) を足した min_length + 1 を出力します。

計算量

• 時間計算量: \(O(N)\) 差分配列 \(D\) の作成に \(O(N)\) かかります。尺取り法では、right と left がそれぞれ最大で \(N-1\) 回ずつしか右に移動しないため、ループ全体の処理回数も \(O(N)\) となります。したがって、全体の時間計算量は \(O(N)\) です。
• 空間計算量: \(O(N)\) 入力を受け取る配列 \(A\) や、差分を保存する配列 \(D\) を持つため、\(O(N)\) のメモリを使用します。

実装のポイント

• 「差分の数」と「地点の数」の違いに注意 配列 \(D\) は「地点と地点の間」を表すため、長さが \(L\) の区間には \(L + 1\) 個の地点が含まれます。最後に答えを出力する際に + 1 を忘れないようにしましょう。

• 尺取り法の while ループ right を進めて条件を満たした（和が \(K\) 以上になった）とき、そこから「条件を満たさなくなるまで」left を進めて区間を縮める処理を while ループで書くのが、尺取り法の定石であり最もシンプルに書ける方法です。

  ソースコード

import sys

def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    
    N = int(data[0])
    K = int(data[1])
    A = [int(x) for x in data[2:N+2]]
    
    if N == 1:
        print(-1)
        return
        
    D = [abs(A[i+1] - A[i]) for i in range(N-1)]
    
    left = 0
    current_sum = 0
    min_length = float('inf')
    
    for right in range(N-1):
        current_sum += D[right]
        while current_sum >= K:
            if right - left + 1 < min_length:
                min_length = right - left + 1
            current_sum -= D[left]
            left += 1
            
    if min_length == float('inf'):
        print(-1)
    else:
        print(min_length + 1)

if __name__ == '__main__':
    solve()

この解説は gemini-3.1-pro-thinking によって生成されました。