「最小値の最大化」 (or 「最大値の最小化」) には二分探索が有効という典型ですね。

類題とか (二分探索以外の問題も含むことと、ハイレベルな問題も多いことに注意)

問題概要

長さ $L$ のようかんがあって、そのうち左端から $A_{1}, \dots, A_{N}$ の位置に切れ目があります。

これら $N$ 個の切れ目の中から $K$ 個の切れ目を選ぶ方法に対して、「切断されたできる $N+1$ 個のようかんの長さの最小値」をスコアと呼ぶことにします。

スコアの最大値を求めてください。

制約

$1 \le K \le N \le 10^{5}$
$0 \lt A_{1} \lt A_{2} \lt \dots \lt A_{N} \lt L \le 10^{9}$

考えたこと

蟻本 P. 131 にも載ってる「Aggressive cows (POJ No.2456)」を AtCoder 上でもジャッジできるようにした問題、という感じですね！

さて、次の判定問題を解くことを考えてみましょう。

スコアを $x$ 以上のすることは可能か？

この判定問題は、次のように言い換えられます。

切断されてできる $K+1$ 個のようかんの長さをすべて $x$ 以上とすることは可能か？

この問題が解ければ、二分探索法によって最適解を求めることができます。つまり、

left ← $-1$
right ← 十分大きな値 (今回は $L+1$ など)

と設定しておいて、mid = (left + right) / 2 として、

スコアを mid 以上とすることが可能なとき：left ← mid
不可能なとき：right ← mid

と更新すればよいでしょう。変数 left は常に「そのスコア以上を達成可能」であることを表し、変数 right は常に「そのスコアを達成不可能」であることを表します。

判定問題

それでは、切断してできるようかんの長さをすべて $x$ 以上にすることが可能かどうかを判定する問題を解いてみましょう。

これは「ようかんの左端から見て行って、前回切断した箇所から見て初めて $x$ 以上の長さとなる切れ目で切断していく」という Greedy で解くことができます。

これによって $x$ 以上の長さの切れ目が $K+1$ 個以上生成できれば可能、そうでなければ不可能と判定できます。

コード

計算量を評価してみましょう。判定問題は $O(N)$ で解けます。二分探索の反復回数は $O(\log L)$ と評価できますので、全体の計算量は $O(N \log L)$ となります。

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

int main() {
    // 入力
    long long N, L, K;
    cin >> N >> L >> K;
    vector<long long> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];

    // 判定問題
    // すべての長さを x 以上にすることが可能か？
    auto check = [&](long long x) -> bool {
        long long num = 0; // 何個に切れたか
        long long pre = 0; // 前回の切れ目
        for (int i = 0; i < N; ++i) {
            // x を超えたら切断
            if (A[i] - pre >= x) {
                ++num;
                pre = A[i];
            }
        }
        // 最後のピースが x 以上なら加算
        if (L - pre >= x) ++num;

        return (num >= K + 1);
    };

    // 二分探索
    long long left = -1, right = L + 1;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        if (check(mid)) left = mid;
        else right = mid;
    }
    cout << left << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

競プロ典型 90 問 001 - Yokan Party（★4）

問題概要

制約

考えたこと

判定問題

コード