C++で最小距離が最大になるようにk個の要素を配置する方法

この記事では、同じ直線上に並ぶ n 個の点の座標が与えられたとき、その中から k 個の要素を選んで配置し、選ばれた要素どうしの最小距離が最大になるようにする問題を解説します。
これは「aggressive cows（アグレッシブ・カウ）問題」としても知られる古典的な最適化問題で、二分探索と貪欲法を組み合わせることで効率的に解くことができます。

問題の概要と入出力例

入力：array = {3, 5, 6, 9, 1, 8}、k = 3

出力：4

配列をソートすると {1, 3, 5, 6, 8, 9} となります。ここで 1・5・9 の3点を選ぶと、隣接する要素間の距離はそれぞれ 4 になり、これ以上大きくすることはできません。したがって答えは 4 です。

解法の考え方：ソート＋二分探索＋貪欲法

この問題の鍵は、「ある距離 d 以上の間隔で k 個の要素を配置できるか？」という判定問題に帰着させることです。この判定には単調性があります。

• d が小さすぎる → 配置は必ず成功する
• d が大きすぎる → 配置は失敗する

そのため、次の手順で解きます。

1. 配列を昇順にソートする。
2. 候補の距離 d に対して、先頭の要素から順に「前回配置した位置から d 以上離れた要素」を貪欲に選んでいき、k 個配置できれば成功と判定する。
3. d を二分探索で絞り込み、条件を満たす最大の d を答えとする。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

// 距離 mid 以上の間隔で k 個の要素を配置できるかを判定する関数
bool canGenerateResult(int mid, int arr[], int n, int k) {
    int pos = arr[0];   // 最初の要素は先頭に固定
    int elements = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] - pos >= mid) {
            pos = arr[i];
            elements++;
            if (elements == k)
                return true;
        }
    }
    return false;
}

// 最小距離の最大値を二分探索で求める関数
int maxMinDist(int arr[], int n, int k) {
    sort(arr, arr + n);
    int res = -1;
    int left = 1, right = arr[n-1] - arr[0];
    while (left <= right) {
        int mid = (left + right) / 2;
        if (canGenerateResult(mid, arr, n, k)) {
            res = max(res, mid);
            left = mid + 1;    // 成功 → より大きな距離を試す
        } else {
            right = mid - 1;   // 失敗 → 距離を縮める
        }
    }
    return res;
}

int main() {
    int arr[] = {3, 5, 6, 9, 1, 8};
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;
    cout << "The maximized minimum distance is : " << maxMinDist(arr, n, k);
    return 0;
}

実装上のポイントは二分探索の範囲設定です。距離の取りうる範囲は 1 ～（最大座標 − 最小座標）なので、left = 1、right = arr[n-1] - arr[0] とすることで、どんな入力に対しても正しい答えが得られます。

実行結果

The maximized minimum distance is : 4

計算量の評価

• ソート：O(n log n)
• 二分探索×貪欲判定：O(n log D)（D は座標の最大値と最小値の差）

全体として非常に効率的なアルゴリズムであり、要素数 n が大きい場合でも高速に動作します。