【C++解説】max−min ≤ K を満たすための配列からの最小削除数を求めるアルゴリズム

問題文

N個の整数と値Kが与えられたとき、残りの要素について Amax − Amin ≤ K が成り立つようにするために削除が必要な要素の最小個数を求めます。要素を削除した後の Amax（最大値）と Amin（最小値）は、残った要素の中から判断します。

例

配列 arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20}、k = 4 の場合、出力は 5 となります。

• 配列の先頭から 1、3、4 を削除する
• 配列の末尾から 17 と 20 を削除する
• 最終的な配列は {9, 10, 11, 12} となり、12 − 9 ≤ 4 を満たす

アルゴリズム

1. 与えられた要素をソートします。
2. 貪欲法の考え方では、最小値または最大値のいずれかを削除し、その都度 Amax − Amin ≤ K が成立しているかを確認するのが最善です。削除の組み合わせは複数考えられるため、それらすべてを検討する必要があります。
3. 削除の方法は「最小値を削除する」か「最大値を削除する」の2通りです。削除後に残る要素のインデックス範囲を (i…j) とし、初期状態では i = 0、j = n−1、削除数は 0 から始めます。
4. a[j] − a[i] > k の場合にのみ要素を削除します。削除方法は (i+1…j) または (i…j−1) の2通りあり、このうち結果が最小となるものを採用します。重複計算を避けるため、メモ化（DPテーブル）を利用しています。

C++実装例

#include <bits/stdc++.h>
#define MAX 100
using namespace std;
int dp[MAX][MAX];
int removeCombinations(int *arr, int i, int j, int k) {
    if (i >= j) {
    return 0;
    } else if ((arr[j] - arr[i]) <= k) {
        return 0;
    } else if (dp[i][j] != -1) {
        return dp[i][j];
    } else if ((arr[j] - arr[i]) > k) {
        dp[i][j] = 1 + min(removeCombinations(arr, i +
        1, j, k),
        removeCombinations(arr, i, j - 1,k));
    }
    return dp[i][j];
}
int removeNumbers(int *arr, int n, int k){
    sort(arr, arr + n);
    memset(dp, -1, sizeof(dp));
    return n == 1 ? 0 : removeCombinations(arr, 0, n - 1,k);
}
int main() {
    int arr[] = {1, 3, 4, 9, 10, 11, 12, 17, 20};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 4;
    cout << "Minimum numbers to be removed = " <<
    removeNumbers(arr, n, k) << endl;
    return 0;
}

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

出力

Minimum numbers to be removed = 5

まとめ

本問題は、ソート後の配列に対して「最小値を取り除く」か「最大値を取り除く」かを選択しながら再帰的に探索することで解けます。メモ化再帰（動的計画法）を組み合わせることで、同じ状態 (i, j) に対する再計算を防ぎ、効率的に最小削除数を求めることができます。