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

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

AtCoder ABC 023 D - 射撃王 (試験管青色)

大昔の ABC の問題ですが、今なお色あせない教育的良問。二分探索の練習問題に。

問題概要

 N 個の風船がそれぞれ初期状態では高度  H_{1}, H_{2}, \dots, H_{N} の位置にあり、1 秒ごとに  S_{1}, S_{2}, \dots, S_{N} ずつ上昇する。これらすべての風船を射撃によって割りたい。

競技開始時に 1 個風船を割ることができ、そこから 1 秒ごとに 1 個の風船を割ることができる。最終的にすべての風船を割りたいですが、どの順番に風船を割るかは自由に選べるものとする。

各風船を割るときに発生するペナルティは、そのときの風船の高度とする。最終的なペナルティは、各風船を割ったときに発生するペナルティの最大値とする。

最終的なペナルティとして考えられる最小値を求めよ。

制約

  •  1 \le N \le 10^{5}
  •  1 \le H_{i}, S_{i} \le 10^{9}
  • 入力はすべて整数

考えたこと

けんちょん本 6.7 節「二分探索法の応用例 (3):最適化問題を判定問題に」で取り上げている。ここではごく簡単に。

一見すると難しい問題に見えてしまうかもしれない。要するに、すべての風船をある程度の高度で割りたいのだ。なので、初めから低い高度にある風船はある程度放置して後回しにしてもよいかもしれない。高い高度にある風船であっても上昇スピードが遅ければ後回しにしてもいいかもしれない。こういうことを考えてると、風船を割る優先順位を定めるのがとても難しそうだ...

しかし、これが次のような判定問題となった途端に、一気に優先順位が決まってくるのだ!!!!!!!


すべての風船を高度  x 以内で割ることは可能か判定せよ。


この判定問題が解けるならば、二分探索法によって十分高速に問題を解くことができる。

判定問題

すべての風船を高度  x 以内に割りたいと、デッドラインを決めた時点で、風船を割る優先順位は自ずと定まってくる。

まず各風船  i について、デッドラインに達するまでの時間を求めることができる。

  •  t_{i} = (x - H_{i}) / S_{i}

という感じだ。これが小さい順、つまりデッドラインが最も差し迫っている順に風船を割っていくのが最適だ。デッドラインが差し迫っている順に風船を割っていって、割り切れたら「可能」、割り切れなかったら「不可能」となる。

コード

計算量は、

  • 判定問題を解く回数: O(\log M) ( M = \max(H_{1} + NS_{1}, \dots, H_{N} + NS_{N}))
  • 判定問題を解く: O(N \log N) (デッドラインが逼迫する順にソートする部分がボトルネック)

ということで、全体として  O(N \log N \log M) となる。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const long long INF = 1LL << 60; // 十分大きい値を 1 つ決める

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

    // 二分探索
    long long left = 0, right = INF;
    while (right - left > 1) {
        long long mid = (left + right) / 2;
        
        // 判定
        bool ok = true;
        vector<long long> t(N, 0); // 各風船を割るまでの制限時間
        for (int i = 0; i < N; ++i) {
            // そもそも mid が初期高度より低かったらfalse
            if (mid < h[i]) ok = false; 
            else t[i] = (mid - h[i]) / s[i];
        }
        // 時間制限がさし迫っている順にソート
        sort(t.begin(), t.end()); 
        for (int i = 0; i < N; ++i) {
            if (t[i] < i) ok = false; // 時間切れ発生
        }

        if (ok) right = mid;
        else left = mid;
    }

    cout << right << endl;
}