「最小値の最大化」 (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)$ となります。

コード (C++)

#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;
}

コード (Python3)

# coding: utf-8
# 入力
N, L = map(int, input().split())
K = int(input())
A = list(map(int, input().split()))

# 判定問題 (すべての長さを x 以上にすることは可能か？)
def check(x):
    num = 0  # 何個切れたか
    pre = 0  # 前回の切れ目
    for i in range(N):
        # x を超えたら切断
        if A[i] - pre >= x:
            num += 1
            pre = A[i]

    # 最後のピースが x 以上なら加算
    if L - pre >= x:
        num += 1

    return (num >= K + 1)

# 二分探索
left, right = -1, L + 1
while right - left > 1:
    mid = (left + right) // 2
    if check(mid):
        left = mid
    else:
        right = mid
print(left)

おまけ

二分探索法の使い方を一通り練習できるサイトとして、アルゴ式で二分探索法のコーナーを作りました。ぜひやってみてください！

algo-method.com

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

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

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

問題概要

制約

考えたこと

判定問題

コード (C++)

コード (Python3)

おまけ