概要

各移動で「\(K\) 以上下がるのはダメ」という条件を式変形すると、ある変換後の数列が非減少になればよい問題に変わります。
すると「変更せずに残せる地点を最大化する問題」になり、最終的には 最長非減少部分列（LNDS） を求めればよいです。

考察

まず、恐怖を感じない条件を扱いやすい形にします。

地点 \(i\) から \(i+1\) への移動で恐怖を感じないための条件は

\(H_i' - H_{i+1}' < K\)

です。整数なので、これは

\(H_i' - H_{i+1}' \le K-1\)

と同じです。ここで

\(D = K-1\)

とおきます。

1. 重要な変形

各地点の高さ \(h_i'\) に対して

\(A_i = h_i' + D(i-1)\)

という値を考えます。すると

\(h_i' - h_{i+1}' \le D\)

は

\(h_i' + D(i-1) \le h_{i+1}' + Di\)

つまり

\(A_i \le A_{i+1}\)

と同値です。

---

つまり、「恐怖を感じない」ことは、変換後の数列 \(A_1,A_2,\dots,A_N\) が非減少であること と全く同じです。

2. 変更しない地点はどんな条件を満たす必要があるか

地点 \(i\) を変更しないなら、その変換後の値は固定で

\(A_i = H_i + D(i-1)\)

です。

また、両端は変更できないので

• \(A_1 = H_1\)
• \(A_N = H_N + D(N-1)\)

で固定です。

数列全体が非減少になるためには、変更しない地点たちの \(A_i\) は

1. 順番通りに並べたとき非減少
2. 両端の間に入るので \(A_1 \le A_i \le A_N\)

を満たさなければなりません。

したがって、変更せずに残せる内部地点の最大個数は、

• 内部地点の値 \(A_i = H_i + D(i-1)\) のうち
• \(A_1 \le A_i \le A_N\) を満たすものだけを対象にして
• その 最長非減少部分列 の長さ

に等しくなります。

3. なぜ部分列だけ見ればよいのか

「部分列として非減少なら、本当に他の地点を適当に変更して埋められるの？」が気になるかもしれません。

これは可能です。
残す地点（両端を含む）を左から順に見て、その変換後の値が

\(a_{p_1} \le a_{p_2} \le \cdots\)

となっていれば、その間の変更する地点には、この範囲に入るような値を自由に入れればよいです。
元の高さは \(h_i' = A_i - D(i-1)\) で復元でき、非負整数にもできます。

よって、「残す地点は非減少部分列になっていれば十分」です。

4. 不可能判定

内部地点を全部変更するとしても、両端だけは固定です。
したがって、そもそも

\(A_1 \le A_N\)

でなければ絶対に不可能です。

これは

\(H_1 \le H_N + D(N-1)\)

すなわち

\(H_1 - H_N \le (K-1)(N-1)\)

ということです。これを満たさないなら答えは -1 です。

5. 素朴解法では間に合わない

最長非減少部分列を普通の DP で求めると \(O(N^2)\) になり、\(N \le 3\times 10^5\) では間に合いません。

そこで、patience sorting による \(O(N \log N)\) の LNDS を使います。

このとき「非減少」なので、二分探索には bisect_right を使うのがポイントです。
（bisect_left だと「狭義増加」になってしまいます。）

アルゴリズム

1. \(D = K-1\) とする。
2. 両端の変換後の値を
   • \(\text{lo} = H_1\)
   • \(\text{hi} = H_N + D(N-1)\) とする。
3. \(\text{lo} > \text{hi}\) なら不可能なので -1 を出力。
4. 内部地点 \(i=2,\dots,N-1\) について
   \(x = H_i + D(i-1)\) を計算する。
5. \(x\) が \(\text{lo} \le x \le \text{hi}\) を満たすものだけ取り出し、その列に対して最長非減少部分列の長さ \(L\) を求める。
6. 内部地点は全部で \(N-2\) 個なので、答えは

\(N-2-L\)

LNDS の求め方

tails[len] を
「長さ len+1 の非減少部分列の、末尾としてありうる最小値」
として持ちます。

各 \(x\) について

• j = bisect_right(tails, x)

とし、

• j == len(tails) なら末尾に追加
• そうでなければ tails[j] = x

と更新します。

最終的な len(tails) が LNDS の長さです。

計算量

• 時間計算量: \(O(N \log N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 「非減少部分列」なので、二分探索は bisect_right を使う。

• 変換後の値は \(A_i = H_i + (K-1)(i-1)\) であることに注意する。

• lo <= x <= hi を満たさない内部地点は、どのみち両端を含む非減少列に入れないので無視してよい。

• N=2 でも同じコードで処理できる。内部地点数が \(0\) 個なので、可能なら答えは 0。

  ソースコード

import sys
from bisect import bisect_right

def solve():
    vals = list(map(int, sys.stdin.buffer.read().split()))
    N, K = vals[0], vals[1]
    D = K - 1

    lo = vals[2]                  # H_1 + D*0
    hi = vals[N + 1] + D * (N - 1)  # H_N + D*(N-1)

    if lo > hi:
        print(-1)
        return

    tails = []
    for i in range(1, N - 1):
        x = vals[2 + i] + D * i
        if lo <= x <= hi:
            j = bisect_right(tails, x)
            if j == len(tails):
                tails.append(x)
            else:
                tails[j] = x

    print(N - 2 - len(tails))

if __name__ == "__main__":
    solve()

---

この解説は gpt-5.4-high によって生成されました。