概要

本問題は、与えられた標高の条件から、高橋君が恐怖を感じない（＝標高の減少が \(K-1\) 以下）という制約を数式で整理し、変更しない地点を最大化する問題、すなわち最長増加部分列（LIS）のバリエーションに帰着して解く問題です。

考察

1. 条件の数式化

地点 \(i\) から \(i+1\) への移動で恐怖を感じない条件は、 $\(H_i - H_{i+1} \leq K - 1\)\( です。これを移行して整理すると、 \)\(H_{i+1} \geq H_i - (K - 1)\)$ となります。

この不等式をすべての隣接する地点について成り立たせる必要があります。ここで、各地点のインデックス \(i\)（1-indexed）を用いて、 $\(A_i = H_i + i \times (K - 1)\)\( という新しい配列 \)A\( を定義します。 すると、上記の条件はすべての \)i\( について、 \)\(A_{i+1} \geq A_i\)$ と、非常にシンプルな広義単調増加の条件に書き換えることができます。

2. 変更しない地点の最大化

地点 \(1\) と地点 \(N\) の標高は変更できません。したがって、\(A_1\) と \(A_N\) の値は固定です。 中間の地点 \(2, \ldots, N-1\) については、標高を任意の非負整数に変更できます。

変更する地点 \(p\) の標高 \(H'_p\) はいくらでも大きくできるため、変更しない地点のインデックスの集合を \(\{1, i_2, i_3, \ldots, N\}\) としたとき、 $\(A_1 \leq A_{i_2} \leq A_{i_3} \leq \ldots \leq A_N\)$ が成り立ってさえいれば、中間の変更する地点の標高を適切に設定して、全体を単調増加にすることが常に可能です。

したがって、この問題は次のように言い換えられます。 「\(A_1 \leq A_{i_2} \leq A_{i_3} \leq \ldots \leq A_N\) を満たすように、変更しない地点のインデックスの集合 \(\{1, i_2, i_3, \ldots, N\}\) を選ぶとき、その要素数（変更しない地点数）の最大値を求めよ。」

これは、配列 \(A\) の中から \(A_1\) 以上 \(A_N\) 以下の要素を取り出し、始点を \(A_1\)、終点を \(A_N\) に固定したときの最長増加部分列（LIS）を求める問題にほかなりません。

アルゴリズム

動的計画法（DP）を用いて最長増加部分列の長さを求めます。

DPの定義

\(DP[i]\) を「地点 \(i\) を最後に選んだ（変更しない）ときの、そこまでの変更しない地点数の最大値」とします。 - 初期値: \(DP[1] = 1\)、その他は \(-\infty\) - 遷移: \(A_1 \leq A_i \leq A_N\) を満たす \(i\) について、 $\(DP[i] = \max_{1 \leq j < i, A_j \leq A_i} (DP[j]) + 1\)\( - **求める値**: \)DP[N]\( が得られれば、最小の変更回数は \)N - DP[N]\( となります。\)DP[N]$ が更新されなかった（始点から到達不可能な）場合は -1 を出力します。

セグメント木による高速化

遷移を素直に行うと \(O(N^2)\) の時間がかかり、実行時間制限（TLE）に間に合いません。 そこで、値 \(A_i\) を座標圧縮した上で、セグメント木（Segment Tree）を使用します。

1. 配列 \(A\) のうち、 \([A_1, A_N]\) の範囲にある値を集めてソート・重複排除し、座標圧縮します。
2. 区間最大値を取得できるセグメント木を初期化し、 \(A_1\) の位置に \(1\) をセットします。
3. \(i = 2\) から \(N-1\) まで順に以下を行います。
   • \(A_1 \leq A_i \leq A_N\) を満たす場合、セグメント木の区間 \([0, A_i]\) の最大値 \(val\) を取得します。
   • \(val \geq 1\) であれば（始点 \(1\) から到達可能であれば）、 \(DP[i] = val + 1\) とし、セグメント木の \(A_i\) の位置を \(DP[i]\) で更新（既存の値との \(\max\) を取る）します。
4. 最後に、 \(A_N\) について同様に区間 \([0, A_N]\) の最大値 \(val\) を取得し、 \(DP[N] = val + 1\) とします。
5. \(DP[N]\) が有効な値であれば \(N - DP[N]\) を、そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(N \log N)\)
  • 座標圧縮のためのソートに \(O(N \log N)\) かかります。
  • セグメント木のクエリと更新は各ステップ \(O(\log N)\) であり、全体で \(O(N \log N)\) となります。
• 空間計算量: \(O(N)\)
  • 配列 \(A\) や座標圧縮用の配列、セグメント木の保持に \(O(N)\) のメモリを使用します。

実装のポイント

• 非負整数の制約について: 中間の変更する地点 \(p\) において、標高を非負にする制約 \(H'_p \geq 0\) は \(A'_p \geq p \times (K-1)\) と同値です。変更しない地点 \(i_j, i_{j+1}\) の間で \(A_{i_j} \leq A_{i_{j+1}}\) が成り立っていれば、中間の \(p\) に対して \(A'_p = \max(A_{i_j}, p \times (K-1))\) と置くことで、単調増加性と非負整数制約を同時に満たす値を常に作ることができます。そのため、DPの遷移においては \(A\) の値の比較だけで十分です。

• セグメント木のモノイド: 区間最大値を取得するため、セグメント木の演算は max、単位元は十分小さな値（-1e9 など）とします。

  ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <atcoder/segtree>

using namespace std;

int op(int a, int b) {
    return max(a, b);
}

int e() {
    return -1e9;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long K;
    if (!(cin >> N >> K)) return 0;

    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }

    vector<long long> A(N);
    for (int i = 0; i < N; ++i) {
        A[i] = H[i] + (i + 1) * (K - 1);
    }

    if (A[0] > A[N - 1]) {
        cout << -1 << "\n";
        return 0;
    }

    vector<long long> vals;
    for (int i = 0; i < N; ++i) {
        if (A[i] >= A[0] && A[i] <= A[N - 1]) {
            vals.push_back(A[i]);
        }
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());

    auto get_pos = [&](long long x) {
        return lower_bound(vals.begin(), vals.end(), x) - vals.begin();
    };

    atcoder::segtree<int, op, e> seg(vals.size());

    int pos0 = get_pos(A[0]);
    seg.set(pos0, 1);

    for (int i = 1; i < N - 1; ++i) {
        if (A[i] >= A[0] && A[i] <= A[N - 1]) {
            int pos = get_pos(A[i]);
            int val = seg.prod(0, pos + 1);
            if (val >= 1) {
                int dp_val = val + 1;
                seg.set(pos, max(seg.get(pos), dp_val));
            }
        }
    }

    int posN = get_pos(A[N - 1]);
    int val = seg.prod(0, posN + 1);
    if (val >= 1) {
        int dp_N = val + 1;
        cout << N - dp_N << "\n";
    } else {
        cout << -1 << "\n";
    }

    return 0;
}

---

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