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

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

競プロ典型 90 問 001 - Yokan Party(★4)

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

前提知識

二分探索にまったく経験がない場合は、まずは次の記事を読んでみてください。

qiita.com

問題概要

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

これら  N 個の切れ目の中から  K 個の切れ目を選ぶことにします。このとき、ようかんは  K+1 個の部分に分かれることになります。

この、切断されたできる  K+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}

考えたこと

この問題は「〜の最小値をスコアとする。その最大値を求めてください」という形をしています。

このように、「最小値を最大化してください」という問題では二分探索が有効であることが多いです!! (最大値の最小化でも同様です)

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


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


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


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


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

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

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

  • スコアを mid 以上とすることが可能なとき:leftmid
  • 不可能なとき:rightmid

と更新すればよいでしょう。変数 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)

類題情報

drken1215.hatenablog.com