概要

この問題は、一列に並んだ \(N\) 枚のブロックのうち最大 \(K\) 枚の高さを自由に変更し、隣り合うブロックの高さの差が \(T\) を超える「危険箇所」の数を最小化する問題です。

\(N \le 10\) という制約が非常に小さいことに着目し、ビット全探索を用いて「高さを変更しないブロック」を全探索することで、最適な置き換え方を効率よく求めることができます。

考察

1. 制約への着目

ブロックの数 \(N\) が最大でも \(10\) と非常に小さいです。このように制約が極端に小さい場合、指数時間（例えば \(O(2^N)\)）の探索を行っても十分に実行時間制限に間に合います。したがって、どのブロックを変更するか（あるいは変更しないか）を全探索する方針が有効です。

2. 「変更しないブロック」を固定する

「変更するブロック」を直接決めるのではなく、「元の高さを維持する（変更しない）ブロック」を固定して考えてみましょう。

変更しないブロックの数を \(m\) とします。このとき、変更するブロックの数は \(N - m\) となります。使える魔法（交換）は最大 \(K\) 回なので、残すブロックの数 \(m\) は以下の条件を満たす必要があります。 $\(m \ge N - K\)$

選んだ「変更しないブロック」のインデックスを、左から順に \(i_1, i_2, \ldots, i_m\) とします。

3. 隣り合う「変更しないブロック」の間で発生する危険箇所

隣り合う「変更しないブロック」のペア \(u = i_j\) と \(v = i_{j+1}\) について考えます。この \(u\) と \(v\) の間にある \(v - u - 1\) 個のブロックはすべて高さを自由に変更できます。

\(u\) から \(v\) までのインデックスの差（距離）を \(L = v - u\) とします。 隣り合うブロックの差をすべて \(T\) 以下に抑えつつ、高さ \(D_u\) から \(D_v\) まで \(L\) 歩でつなぐことができるでしょうか？

1歩あたりに変化できる高さは最大で \(T\) なので、\(L\) 歩で変化できる高さの最大値は \(L \times T\) です。 したがって、以下の条件が成り立ちます。

• \(|D_u - D_v| \le L \times T\) のとき 間のブロックの高さをうまく等間隔に調整することで、すべての隣り合う段差を \(T\) 以下にできます。この区間での危険箇所は \(0\) にできます。
• \(|D_u - D_v| > L \times T\) のとき どのように間の高さを決めても、どうしても1箇所以上は差が \(T\) を超えてしまいます。この場合、1箇所だけに大きな段差を押し付け、残りの \(L-1\) 箇所は差を \(T\) 以下に抑えることができるため、この区間での危険箇所の最小値は \(1\) になります。

また、最初の「変更しないブロック」より左側、および最後の「変更しないブロック」より右側にあるブロックは、外側に制約がないため、すべて高さを適切に調整して危険箇所を \(0\) にできます。

したがって、「変更しないブロック」の集合を固定したとき、発生する危険箇所の最小値は、「隣り合う変更しないブロックのペア \((u, v)\) のうち、 \(|D_u - D_v| > (v - u) T\) を満たすものの個数」と一致します。

アルゴリズム

1. コーナーケースの処理 \(K \ge N - 1\) の場合、すべてのブロック（または1つを除くすべて）を変更できるため、必ず危険箇所を \(0\) にできます。この場合は即座に 0 を出力して終了します。
2. ビット全探索 \(1\) から \(2^N - 1\) までのビットマスクを用いて、変更しないブロックの集合を全探索します。
   • マスクから、変更しないブロックのインデックスのリスト idxs を作成します。
   • idxs の要素数 \(m\) が \(N - K\) 未満である場合は、変更するブロックが \(K\) 枚を超えてしまうためスキップします。
   • idxs の隣り合う要素のペア \((u, v) = (\text{idxs}[j], \text{idxs}[j+1])\) すべてについて、 \(|D_u - D_v| > (v - u) T\) が成り立つかを判定し、成り立つ場合は危険箇所のカウントを \(+1\) します。
   • すべての有効なマスクについて危険箇所のカウントの最小値を求め、それを出力します。

計算量

• 時間計算量: \(O(N \cdot 2^N)\) 「変更しないブロック」の選び方は \(2^N\) 通りあり、各選び方に対して隣り合う要素の判定に \(O(N)\) の時間がかかります。 \(N \le 10\) のとき、 \(10 \cdot 2^{10} \approx 10^4\) 回程度の計算となり、実行時間制限（通常 2.0 秒）に対して一瞬で動作します。

• 空間計算量: \(O(N)\) 入力の配列 \(D\) や、一時的に作成するインデックスのリスト idxs のサイズは最大でも \(N\) であり、極めて省メモリです。

実装のポイント

• コーナーケースの早期リターン \(K \ge N - 1\) のとき、ビット全探索のロジックでは「残すブロックが \(1\) つ以下」になり、隣り合うペアが存在しなくなるため正しく計算できない可能性があります。最初にこのケースを排除しておくことで、実装がシンプルになりバグを防げます。

• ビット演算 \(i\) 番目のブロック（0-indexed）を残すかどうかは、(mask >> i) & 1 が 1 であるかによって判定できます。

  ソースコード

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

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

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

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

    if (K >= N - 1) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = N;

    for (int mask = 1; mask < (1 << N); ++mask) {
        vector<int> idxs;
        for (int i = 0; i < N; ++i) {
            if ((mask >> i) & 1) {
                idxs.push_back(i);
            }
        }

        int m = idxs.size();
        if (m < N - K) continue;

        int current_cost = 0;
        for (int j = 0; j < m - 1; ++j) {
            int u = idxs[j];
            int v = idxs[j + 1];
            long long L = v - u;
            long long diff = abs(D[u] - D[v]);
            if (diff > L * T) {
                current_cost += 1;
            }
        }
        ans = min(ans, current_cost);
    }

    cout << ans << "\n";

    return 0;
}

---

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