概要

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

変更しないブロックをいくつか残し、それらの位置関係と高さの関係に着目することで、動的計画法（DP）を用いて効率的に解くことができます。

考察

1. 変更するブロックの自由度

変更対象に選んだブロックは、高さを任意の整数に設定できます。上限や下限はありません。

2. 変更しない2つのブロックの間に注目する

いま、変更しないブロックを左から順にいくつか選ぶことを考えます。 隣り合う「変更しないブロック」が \(p\) 番目と \(i\) 番目（\(p < i\)）であるとし、その間にある \(i - p - 1\) 個のブロックはすべて変更するとします。

このとき、\(p\) 番目から \(i\) 番目までの間（計 \(i - p\) 個の隣接ペア）で、危険箇所（差が \(T\) を超える箇所）の数を最小でいくつにできるでしょうか？

1ステップ（隣り合うブロック間）で許容される最大の高さの変化量は \(T\) です。したがって、\(i - p\) ステップ全体で埋められる最大の高さの差は \((i - p) \times T\) となります。

• \(|D_i - D_p| \leq (i - p) \times T\) のとき： 間のブロックの高さをうまく等間隔に設定することで、すべての隣接ペアの差を \(T\) 以下に抑えることができます。したがって、この区間における危険箇所の数は \(0\) にできます。
• \(|D_i - D_p| > (i - p) \times T\) のとき： どのように間の高さを設定しても、どうしても少なくとも1箇所は差が \(T\) を超えてしまいます。しかし、1箇所だけに大きな段差を集め、残りの \(i - p - 1\) 箇所を差 \(T\) 以下に抑えるように設定すれば、危険箇所の数を最小の \(1\) に抑えることができます。

このように、変更しないブロック \(p\) と \(i\) の間の最小コスト（危険箇所の数）は、以下のようにシンプルに定まります。

\[ \text{cost}(p, i) = \begin{cases} 0 & (\text{if } |D_i - D_p| \leq (i - p) \times T) \\ 1 & (\text{otherwise}) \end{cases} \]

3. 端の処理

最初の「変更しないブロック」より左側、および最後の「変更しないブロック」より右側については、片側の高さが固定されていない（自由に動かせる）ため、常に危険箇所を \(0\) にできます。

4. 動的計画法（DP）への帰着

以上の考察から、この問題は「変更しないブロックをいくつか選び、選んだブロック間のコストの総和を最小化する」という問題に帰着されます。

アルゴリズム

以下のような動的計画法（DP）を定義します。

DPテーブルの定義

• dp[i][c] : \(i\) 番目のブロックを変更せず、これを含めて左から \(c\) 個のブロックを変更しないとしたときの、そこ（\(1\) から \(i\) 番目まで）の最小危険箇所数。

初期化

1つ目の変更しないブロックを \(i\) とするとき、それより左側はすべて変更するため、危険箇所は \(0\) です。 - dp[i][1] = 0 （\(1 \leq i \leq N\)） - それ以外の値は無限大（\(\infty\)）で初期化します。

遷移

\(c\) 個目（\(c \geq 2\)）の変更しないブロックとして \(i\) 番目を選ぶとき、その直前の変更しないブロック \(p\)（\(c-1 \leq p < i\)）から遷移します。

\[ \text{dp}[i][c] = \min_{c-1 \leq p < i} \left( \text{dp}[p][c-1] + \text{cost}(p, i) \right) \]

答えの導出

変更するブロックの数は最大 \(K\) 個なので、変更しないブロックの数 \(c\) は、少なくとも \(N - K\) 個以上必要です（ただし、少なくとも1個は選ぶため \(c \geq 1\)）。

したがって、 \(c \geq \max(1, N - K)\) を満たす \(c\) について、最後の変更しないブロックを \(i\) としたときの dp[i][c] の最小値が答えとなります。 （最後の変更しないブロック \(i\) より右側はすべて変更するため、追加のコストはかかりません）

※ \(K \geq N\) の場合は、すべてのブロックを変更できるため、無条件で答えは \(0\) となります。

計算量

• 時間計算量: \(O(N^3)\) DPの状態数が \(O(N^2)\) であり、各状態に対する遷移に \(O(N)\) かかります。 制約が \(N \leq 10\) と非常に小さいため、最悪でも \(10^3 = 1000\) 回程度のループとなり、一瞬で実行が完了します。
• 空間計算量: \(O(N^2)\) DPテーブルのサイズは \((N+1) \times (N+1)\) であり、メモリ制限に対して十分に余裕があります。

実装のポイント

• インデックスの調整: 問題文は 1-indexed（1から \(N\)）で考えると分かりやすいため、コード内でも 1-indexed でDPを構成しています。配列 D から値を取り出す際は D[i-1] や D[p-1] のように 0-indexed に変換してアクセスしています。

• コーナーケースの処理: \(K \geq N\) のときは、DPを回す前に 0 を出力して早期リターンすることで、配列の範囲外参照などのバグを防いでいます。

  ソースコード

import sys

def solve():
    # 入力を一括で取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    T = int(input_data[1])
    K = int(input_data[2])
    D = [int(x) for x in input_data[3:]]
    
    # すべてのブロックを変更できる場合は危険箇所を 0 にできる
    if K >= N:
        print(0)
        return

    # dp[i][c]: i 番目のブロックを変更せず、そこまでに変更しないブロックを c 個選んだときの最小危険箇所数
    dp = [[float('inf')] * (N + 1) for _ in range(N + 1)]
    
    # 1つ目の変更しないブロックを選ぶ場合、それより左側はすべて変更するためコストは 0
    for i in range(1, N + 1):
        dp[i][1] = 0
        
    # DPの遷移
    for c in range(2, N + 1):
        for i in range(c, N + 1):
            min_val = float('inf')
            for p in range(c - 1, i):
                # p 番目と i 番目のブロックを変更しないときのコスト
                cost = 1 if abs(D[i-1] - D[p-1]) > (i - p) * T else 0
                val = dp[p][c-1] + cost
                if val < min_val:
                    min_val = val
            dp[i][c] = min_val
            
    # 変更しないブロックの数は、少なくとも N - K 個以上必要
    min_c = max(1, N - K)
    ans = float('inf')
    for c in range(min_c, N + 1):
        for i in range(c, N + 1):
            if dp[i][c] < ans:
                ans = dp[i][c]
                
    print(ans)

if __name__ == '__main__':
    solve()

---

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