【C++】配列上のポイントを選択して最小距離を最大化する方法（二分探索による解法）

問題概要

この問題では、N個のインデックス位置を表す n 個の要素からなる配列 arr[] と、C個の磁石が与えられます。目的は、最も近い2つの磁石の間の距離ができるだけ大きくなるように、すべての磁石を配置することです。

入力例

array = { 1, 4, 6, 12, 28, 44 }、C = 4

出力例

11

解法のアプローチ

この種の「最大化したい最小値を求める」問題は、二分探索（バイナリサーチ）を用いることで効率的に解くことができます。基本的な考え方は次のとおりです。

• まず、仮の最大距離 mid を固定します。
• その距離 mid 以上の間隔を保ちながら、C個の磁石をすべて配置できるかどうかを判定します。
• 配置可能であれば、mid を答えの候補として記録し、さらに大きな距離を試すために探索範囲の下限を上げます。
• 配置できなければ、条件が厳しすぎるため探索範囲の上限を下げます。
• この処理を二分探索が終了するまで繰り返し、答えとなる最大の最小距離を求めます。

配置可能性の判定（canPlace 関数）

判定には貪欲法（グリーディ法）を使います。先頭の位置に最初の磁石を置き、以降は直前に置いた磁石との距離が mid 以上になる位置に順番に磁石を設置していきます。最終的に C個すべて置ければ true を返します。

実装例

以下は、この解法をC++で実装したサンプルプログラムです。

#include <iostream>
using namespace std;

// 距離 mid を保って C個の磁石を配置できるか判定する関数
bool canPlace(int arr[], int n, int C, int mid){
    int magnet = 1, currPosition = arr[0];
    for (int i = 1; i < n; i++) {
        if (arr[i] - currPosition >= mid) {
            magnet++;
            currPosition = arr[i];
            if (magnet == C)
                return true;
        }
    }
    return false;
}

// 二分探索で最大の最小距離を求める関数
int minDistMax(int n, int C, int arr[]){
    int lo, hi, mid, ans;
    lo = 0;
    hi = arr[n - 1];
    ans = 0;
    while (lo <= hi) {
        mid = (lo + hi) / 2;
        if (!canPlace(arr, n, C, mid))
            hi = mid - 1;   // 配置不可 → 上限を下げる
        else {
            ans = max(ans, mid); // 配置可 → 答えを更新
            lo = mid + 1;        // より大きい距離を探索
        }
    }
    return ans;
}

int main(){
    int C = 4;
    int arr[] = { 1, 4, 6, 12, 28, 44 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
    return 0;
}

出力結果

Maximised Minimum distance is 11

計算量について

配置可能性の判定は配列を一度走査するだけで O(n)、二分探索の繰り返し回数は探索範囲の対数オーダー O(log D)（D は最大距離）であるため、全体の計算量は O(n log D) となります。要素数が多い場合でも高速に動作するのがこの手法の大きな利点です。

まとめ

「最小値の最大化」タイプの問題は、二分探索と貪欲法の組み合わせが定石です。本記事のように、距離 mid を固定して判定関数を作り、二分探索で最適値を絞り込む流れを覚えておくと、類似の競技プログラミング問題にも応用できます。