概要

この問題は、与えられた山岳の標高のうち、変更しない地点の数を最大化（＝変更する地点数を最小化）する問題です。 「1歩で下がれる標高の最大値が \(K-1\) 以下である」という条件を、変数変換によって最長増加部分列（LIS: Longest Increasing Subsequence）の問題に帰着させて解くことができます。

考察

1. 恐怖を感じない条件の整理

高橋君が地点 \(i\) から地点 \(i+1\) へ移動するときに恐怖を感じないための条件は、標高の下がり幅が \(K\) 未満であることです。 標高はすべて整数であるため、これは下がり幅が \(K-1\) 以下であることと同値です。 \(D = K - 1\) とおくと、条件は以下のように表せます。

\[H_i - H_{i+1} \leq D \iff H_{i+1} \geq H_i - D\]

2. 複数ステップ離れた地点間の条件

変更しない地点をいくつか選んだとします。隣り合う「変更しない地点」のインデックスを \(i\) と \(j\) （\(i < j\)）とします。 この間にある地点 \(i+1, \ldots, j-1\) の標高を自由に変更して、全体として恐怖を感じずに移動できるようにするためには、どのような条件が必要でしょうか。

\(1\) ステップで最大 \(D\) までしか下がれないため、 \(j - i\) ステップでは最大 \((j - i)D\) までしか下がることができません。 したがって、以下の条件が必須となります。

\[H_j \geq H_i - (j - i)D\]

逆に、この条件が満たされていれば、間の地点の標高を \(H_k = \max(0, H_i - (k - i)D)\) のように設定することで、常に下がり幅を \(D\) 以下に抑えつつ、地点 \(j\) まで到達させることができます（標高の上昇量には制限がないため、途中で \(0\) になっても問題ありません）。

3. 変数変換による簡略化

上記の条件式を整理してみましょう。

\[H_j \geq H_i - j \cdot D + i \cdot D\]

\[H_j + j \cdot D \geq H_i + i \cdot D\]

ここで、各地点 \(i\) について新しい値 \(A_i = H_i + i \cdot D\) （1-based index）を定義します。すると、条件は以下のように非常にシンプルな形になります。

\[A_j \geq A_i\]

これは、「変更しない地点のインデックスに対応する \(A\) の値が、広義単調増加（同じかそれ以上）になっていなければならない」ということを意味します。

4. 最長増加部分列（LIS）への帰着

変更する地点数を最小化することは、変更しない地点数 \(M\) を最大化することと同じです。 地点 \(1\) と地点 \(N\) は変更できないため、必ず「変更しない地点」に含まれます。

したがって、この問題は以下のように言い換えられます。 - \(A_1\) から始まり \(A_N\) で終わる、 \(A\) の広義単調増加な部分列の最大長 \(M\) を求める。

もし \(A_1 > A_N\) である場合は、どのように標高を変更しても不可能なため、答えは -1 となります。 それ以外の場合は、 \(A_1 \leq A_i \leq A_N\) を満たす途中の要素 \(A_i\)（\(1 < i < N\)）をうまく選んで、広義単調増加な部分列を構築します。この最大長 \(M\) が求まれば、変更する地点数の最小値は \(N - M\) となります。

アルゴリズム

広義単調増加な部分列の最大長は、二分探索を用いた動的計画法（DP）により \(O(N \log N)\) で求めることができます。

1. \(D = K - 1\) とし、各 \(i\)（\(0 \leq i \leq N-1\)）について \(A_i = H_i + (i + 1) \cdot D\) を計算します（0-indexed に合わせるため、 \(i+1\) を掛けます）。
2. \(A_0 > A_{N-1}\)（元の \(A_1 > A_N\)）であれば -1 を出力して終了します。
3. DP配列 dp を用意します。dp[len] は「長さ len + 1 の有効な部分列の末尾の最小値」を表します。初期値はすべて \(\infty\) とし、dp[0] = A_0 とします。
4. 各 \(i = 1, 2, \ldots, N-2\) について、 \(A_0 \leq A_i \leq A_{N-1}\) を満たす場合のみ、以下の更新を行います。
   • dp 配列の中で \(A_i\) 以下の要素の数を二分探索（bisect_right）で求め、その位置（インデックス idx）の値を \(A_i\) で更新します。
5. 最後に、 \(A_{N-1}\) を部分列の末尾に追加できる最大の長さを二分探索で求めます。この長さを \(M\) とすると、答えは \(N - M\) となります。

計算量

• 時間計算量: \(O(N \log N)\) 各要素に対して二分探索（bisect_right）を \(1\) 回行うため、全体の計算量は \(O(N \log N)\) となり、 \(N = 3 \times 10^5\) でも実行時間制限に十分間に合います。
• 空間計算量: \(O(N)\) 配列 \(A\) および DP 配列を保持するために必要なメモリは \(O(N)\) です。

実装のポイント

• 境界条件の扱い: 地点 \(1\) と地点 \(N\)（コード内では A[0] と A[N-1]）は変更できないため、途中の要素 \(A_i\) を選ぶ際は必ず \(A_0 \leq A_i \leq A_{N-1}\) の範囲に収まっている必要があります。この条件を満たさない要素は無視することで、端点の制約を正しく反映できます。

• 広義単調増加: 同じ値の連続を許容するため、二分探索には bisect_left ではなく bisect_right を使用します。これにより、同じ値が出現したときに正しく部分列の長さを伸ばすことができます。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    K = int(input_data[1])
    H = [int(x) for x in input_data[2:]]
    
    D = K - 1
    
    # A_i = H_i + i * D (1-based index)
    A = [H[i] + (i + 1) * D for i in range(N)]
    
    A_1 = A[0]
    A_N = A[N - 1]
    
    if A_1 > A_N:
        print(-1)
        return
    
    # dp[len] stores the minimum end value of a valid subsequence of length len + 1
    dp = [float('inf')] * (N + 1)
    dp[0] = A_1
    
    for i in range(1, N - 1):
        val = A[i]
        if A_1 <= val <= A_N:
            idx = bisect_right(dp, val)
            dp[idx] = val
            
    idx = bisect_right(dp, A_N)
    ans_len = idx + 1
    
    print(N - ans_len)

if __name__ == '__main__':
    solve()

---

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