問題リンク

https://www.luogu.org/problemnew/show/P2678

問題背景

年一度の「岩場飛び」大会が開催されます！

問題説明

この大会は一直線の川で行われ、川の中には大きな岩が点在しています。主催者はすでに2つの岩をスタート地点とゴール地点として選定しました。スタートとゴールの間にはN個の岩（スタートとゴールを含まない）があります。競技中、参加者はスタート地点から出発し、隣の岩へ一つずつ飛び移り、ゴールに到達します。

競技の難易度を高めるため、主催者はいくつかの岩を撤去して、競技中の最短飛距離をできるだけ長くしようと計画しています。予算の制約上、主催者はスタートとゴールの間から最大M個の岩（スタートとゴールの岩は除く）を撤除できます。

入出力形式

入力形式：

最初の行には3つの整数L、N、Mが含まれ、それぞれスタートからゴールまでの距離、スタートとゴール間の岩の数、および主催者が最大で撤去できる岩の数を示します。L≥1、N≥M≥0であることが保証されています。

次のN行には、各行に1つの整数が含まれます。i行目の整数Di(0<Di<L)は、i番目の岩がスタート地点からどれだけ離れているかを示します。これらの岩はスタートからの距離の順に並んでおり、2つの岩が同じ位置にあることはありません。

出力形式：

1つの整数、つまり最短飛距離の最大値。

入出力例

25 5 2 
2
11
14
17 
21

4

問題解説

入出力例1の説明：スタートから距離2と14にある岩を2つ撤去すると、最短飛距離は4になります（距離17の岩から距離21の岩へ飛ぶ、または距離21の岩からゴールへ飛ぶ）。

データ範囲について： - 20%のデータ：0≤M≤N≤10 - 50%のデータ：0≤M≤N≤100 - 100%のデータ：0≤M≤N≤50,000、1≤L≤1,000,000,000

解法

まずデータ範囲を見ると、暴力的な列挙では時間が間に合わないことがわかります（部分点を狙う場合は別です）。ここで新しいアルゴリズムである二分探索を使用する必要があります。

二分探索とは？

名前の通り、二分探索はデータセットを毎回2つに分割し、大きな問題を小さな問題に変換するものです。例えば、1から100の数を当てるゲームでは、まず50と当て、小さければ75、大きければ25と当てていくように、最終的に答えを見つけます。

このゲームで毎回当てる数が求める範囲の中間の値であり、これが二分探索の基本的な考え方です。

二分探索が適用できる条件：

• 明確な範囲があること
• 答えが一つに定まること
• 単調性（連続的な増加または減少）を満たすこと

二分探索の2つの形式：

上記は詳細処理に関する説明です。

この問題への適用：

二分探索を理解したところで、この古典的な問題を見ていきましょう。

問題文の中の「競技中の最短飛距離をできるだけ長くする」という一文に注目します。最小値を最大化、または最大値を最小化する問題、あるいは最大値や最小値を求める問題では、二分探索を検討する価値があります。

明らかに、この問題では最短距離を求めているので、二分探索の対象も最短距離です。

まず、答えの単調性を検証します：岩を多く撤去すればするほど、最短飛距離は大きくなります。これが答えの単調性です。

次に実装に移ります。最短飛距離をmidと仮定すると、明らかに0<mid<Lなので、左端点l=0、右端点r=Lとし、毎回midを中間値mid=(l+r+1)>>1として取ります。ここでは第2の形式を使用しています。次に、このmidが有効かどうかを判断するcheck関数を書きます。有効であれば、より大きな値があるか探します（l=mid）。無効であれば、midを小さくします（r=mid-1）。

では、check関数はどのように書くのでしょうか？各岩を一通り調べ、間隔がmid「以下」の岩がいくつあるかを数えます。もし「超過」したらm個なら無効、「以下」なら有効です。

コード例：

#include <iostream>
using namespace std;

int n, m, L;
int b[50005];  // 岩の位置を格納する配列

bool check(int x) {  // 最短飛距離xが有効かチェック
    int previous = 0;  // 前の岩の位置
    int removed = 0;    // 撤去した岩の数
    
    for (int i = 1; i <= n + 1; i++) {  // 各岩をチェック
        if (b[i] - previous < x) {  // 間隔がxより小さい場合
            removed++;  // 岩を撤去
        } else {
            previous = b[i];  // 岩を保持
        }
    }
    
    return removed <= m;  // 撤去数が制限以内なら有効
}

int main() {
    cin >> L >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    b[n + 1] = L;  // ゴール地点を追加
    
    int left = 1, right = L;  // 最短飛距離の境界
    while (left < right) {
        int mid = (left + right + 1) >> 1;  // 中間値を計算
        if (check(mid)) {
            left = mid;  // より大きな値を探す
        } else {
            right = mid - 1;  // 値を小さくする
        }
    }
    
    cout << left;  // 結果を出力
    return 0;
}