概要

この問題は、地点 \(1\) から 地点 \(N\) まで移動する際、どの隣接する地点間でも標高の減少幅を \(K-1\) 以下に抑えつつ、書き換える地点の数を最小化（＝元の標高を維持する地点の数を最大化）する問題です。

考察

条件の言い換え

「標高が \(K\) 以上下がる場合に恐怖を感じる」という条件は、恐怖を感じないためにはすべての \(i\) について以下の式が成り立つ必要があることを意味します。 $\(H_i - H_{i+1} \leq K - 1\)\( ここで \)D = K - 1\( とおくと、条件は \)H_{i+1} \geq H_i - D\( と書けます。これを地点 \)i\( から地点 \)j\( (\)i < j\() までの関係に広げると、以下のようになります。 \)\(H_j \geq H_i - (j - i)D\)$

この式を整理すると、インデックス \(i\) と標高 \(H_i\) を組み合わせた形に変形できます。 $\(H_j + j \cdot D \geq H_i + i \cdot D\)$

数列の変換

新しい数列 \(A\) を \(A_i = H_i + i \cdot D\) と定義すると、条件は 「選んだ地点のインデックス \(i, j\) (\(i < j\)) において \(A_i \leq A_j\) が成り立つ」、つまり数列 \(A\) が広義単調増加であればよいことになります。

固定された端点

地点 \(1\) と地点 \(N\) は標高を変更できません。したがって、以下の条件をまず確認する必要があります。 1. \(A_1 \leq A_N\) であること。これが満たされない場合、どのように中間地点を書き換えても条件を満たせないため、答えは -1 です。 2. 途中の地点 \(i\) (\(1 < i < N\)) をそのまま使うためには、\(A_1 \leq A_i \leq A_N\) を満たしている必要があります。

この条件を満たす中間地点の \(A_i\) を並べたとき、その中から 「広義単調増加（値が減らない）」 となるように最大何個の要素を選べるか、という問題に帰着されます。

アルゴリズム

1. \(D = K - 1\) とする。
2. 各地点 \(i\) について、\(A_i = H_i + (i-1) \cdot D\) を計算する（0-indexedの場合は \(A_i = H_i + i \cdot D\)）。
3. \(A_0\) と \(A_{N-1}\) を比較し、\(A_0 > A_{N-1}\) ならば -1 を出力する。
4. \(1 \leq i \leq N-2\) の範囲で、\(A_0 \leq A_i \leq A_{N-1}\) を満たす \(A_i\) を順に抽出して新しいリスト target を作る。
5. target に対して 最長増加部分列 (LIS) 、正確には 最長非減少部分列 (Longest Non-Decreasing Subsequence) の長さを求める。
   • 二分探索（bisect_right）を用いることで効率的に計算できる。
6. (書き換え可能な地点数 \(N-2\)) - (最長非減少部分列の長さ) が答えとなる。

計算量

• 時間計算量: \(O(N \log N)\)
  • 数列 \(A\) の構築に \(O(N)\)。
  • 最長非減少部分列の計算に \(O(N \log N)\)。
• 空間計算量: \(O(N)\)
  • 数列 \(A\) や LIS 計算用の配列を保持するために必要。

実装のポイント

• 最長非減少部分列の計算: 通常の LIS（厳密に増加）では bisect_left を使いますが、今回は同じ値が続いても良いため bisect_right を使用します。

• 標高の非負整数制約: 問題文に「非負整数値に変更できる」とありますが、変更後の標高の上限がないため、十分大きな値を設定することで必ず \(A_i \leq A_{i+1}\) を満たすように調整可能です。そのため、LIS の計算において非負制約を直接気にする必要はありません。

• インデックスの扱い: 実装では 0-indexed で計算を行うため、地点 \(i\) (\(1 \leq i \leq N\)) を \(0 \leq i \leq N-1\) として扱い、\(A_i = H_i + i \cdot D\) と計算するとスムーズです。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    # Fast input reading
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # Check if we have at least N and K
    if len(input_data) < 2:
        return
        
    N = int(input_data[0])
    K = int(input_data[1])
    
    # Altitudes H_1, ..., H_N
    H = list(map(int, input_data[2:]))
    
    # Descent limit: H_i - H_{i+1} <= K - 1
    # Let D = K - 1. The condition is H_i - H_{i+1} <= D.
    # This is equivalent to H_{i+1} >= H_i - D.
    # By induction, for any i < j, H_j >= H_i - (j - i) * D.
    # This can be rewritten as H_j + j * D >= H_i + i * D.
    # Let A[i] = H[i] + i * D (using 0-based indexing for i).
    # The condition becomes A[j] >= A[i] for any kept indices i < j.
    
    D = K - 1
    
    # Points 1 and N are fixed (indices 0 and N-1)
    # They must satisfy the descent condition: H_N >= H_1 - (N - 1) * D
    A_start = H[0] + 0 * D
    A_end = H[N - 1] + (N - 1) * D
    
    if A_start > A_end:
        print("-1")
        return
        
    # We want to keep the maximum number of original H[i] for 1 <= i <= N-2
    # such that A_start <= A[i] <= A_end and the kept A[i] are non-decreasing.
    target = []
    for i in range(1, N - 1):
        val = H[i] + i * D
        # A point i can be kept only if it's reachable from H_1 and can reach H_N
        if A_start <= val <= A_end:
            target.append(val)
    
    # Longest Non-Decreasing Subsequence (LNDS) of target
    # tails[i] will store the smallest tail of all non-decreasing subsequences of length i+1
    tails = []
    for x in target:
        # Use bisect_right to find the position to maintain non-decreasing order
        idx = bisect_right(tails, x)
        if idx < len(tails):
            tails[idx] = x
        else:
            tails.append(x)
    
    max_kept_middle = len(tails)
    # The answer is the number of middle points minus the maximum number we could keep
    print((N - 2) - max_kept_middle)

if __name__ == "__main__":
    solve()

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