概要

連続した地点からなるルートのうち、隣接地点間の標高差の合計（総高低差）が \(K\) 以上となるものの中で、地点数が最小のものを求める問題。

考察

この問題では、地点 \(l\) から \(r\) までの区間の「総高低差」が

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

で定義されています。これは、隣接する地点の標高差の絶対値を前計算しておけば、区間和として効率的に求められます。

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

単純には、全ての区間 \([l, r]\) を試して、総高低差が \(K\) 以上になるか調べる方法があります。しかし、この方法では区間の個数が \(O(N^2)\) となり、\(N\) が最大 \(2 \times 10^5\) なので現実的ではありません（TLEになります）。

解決策：二分探索＋尺取り法

最小の地点数（つまり区間長）を求めたいので、「地点数 \(x\) で条件を満たす区間が存在するか？」という判定問題を考えます。これは二分探索によって解けます。

さらに、各地点数に対して、条件を満たす区間が存在するかを高速に判定する必要があります。隣接差分の累積和を用いることで、区間和を \(O(1)\) で求めることができます。そして、固定長の区間和のうち、最大値が \(K\) 以上かどうかを尺取り法（スライディングウィンドウ）で求めることで、各判定を線形時間で行えます。

アルゴリズム

1. 隣接する地点の標高差の絶対値を前計算し、配列 diff とする： $\( \text{diff}[i] = |A_{i+1} - A_i| \)$

2. diff の累積和を計算し、配列 prefix とする： $\( \text{prefix}[i] = \sum_{j=0}^{i-1} \text{diff}[j] \)$

3. 地点数 \(len\) について二分探索を行う：

   • 区間長 \(len - 1\) の diff の区間和が \(K\) 以上となるものが存在するかを判定。
   • これは、prefix[j] - prefix[i] >= K となる \(i, j\) （ただし \(j - i = len - 1\)）が存在するかを尺取り法で判定。

4. 条件を満たす最小の \(len\) を出力。存在しなければ -1。

計算量

• 時間計算量: \(O(N \log N)\)
  各二分探索ステップで尺取り法による線形判定を行うため、全体で \(O(N \log N)\)。
• 空間計算量: \(O(N)\)
  diff および prefix 配列に \(O(N)\) のメモリを使用。

実装のポイント

• 累積和を用いて区間和を高速に計算すること。

• 二分探索の範囲を 1 から N とし、mid = 1 のときの処理に注意（区間長が0になるため、常に不可能）。

• 尺取り法で区間和の最大値を効率良く計算し、条件判定を行う。

  ソースコード

import sys
from itertools import accumulate

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

    # Compute the absolute differences
    diff = [abs(A[i+1] - A[i]) for i in range(N-1)]
    
    # If K is 0, we can always take a single point
    if K == 0:
        print(1)
        return
    
    # Prefix sums of differences
    prefix = [0] + list(accumulate(diff))
    
    # Binary search on the answer (number of points in route)
    # The number of points is len = r - l + 1 => r - l = len - 1
    # So total difference is prefix[r] - prefix[l]
    # We want to find minimal len such that there exists r-l = len-1 with prefix[r] - prefix[l] >= K
    
    def possible(length):
        # Check if there's any subarray of consecutive differences of length (length-1) 
        # whose sum is at least K
        if length == 1:
            return False  # Since K > 0 and sum of 0 terms is 0
        window_len = length - 1
        if window_len > len(prefix) - 1:
            return False
        for i in range(len(prefix) - window_len):
            j = i + window_len
            if prefix[j] - prefix[i] >= K:
                return True
        return False

    # More efficient check using sliding window minimum
    def possible_efficient(length):
        if length == 1:
            return False
        window_len = length - 1
        if window_len > len(prefix) - 1:
            return False
        for i in range(len(prefix) - window_len):
            j = i + window_len
            if prefix[j] - prefix[i] >= K:
                return True
        return False

    # Even more efficient: monotonic queue approach for large inputs -> but since we're doing binary search 
    # over answers and checking feasibility each time, let's optimize the feasibility check.
    
    left = 1
    right = N
    answer = -1
    
    while left <= right:
        mid = (left + right) // 2
        # We want to check if there's a subarray of 'diff' of length (mid - 1) with sum >= K
        window_size = mid - 1
        found = False
        
        if window_size == 0:
            # mid=1 => only one point => sum = 0 < K (since K>0), so not valid
            found = False
        elif window_size > len(diff):
            found = False
        else:
            # Sliding window maximum of size window_size in diff array
            current_sum = sum(diff[:window_size])
            if current_sum >= K:
                found = True
            else:
                for i in range(window_size, len(diff)):
                    current_sum += diff[i] - diff[i - window_size]
                    if current_sum >= K:
                        found = True
                        break
        if found:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
            
    print(answer)

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。