[AtCoder] ABC023 D – 射撃王

2020年2月20日AtCoder最大値,二分探索,最小値

問題概要

問題へのリンク

風船に 1 から N までの番号が付けられていて、風船 i (1≦i≦N) は競技開始時に高度 \(H_i\) のところにあり、1 秒経過するにつれて高度が \(S_i\) だけ増加する。
はじめ1つ風船を割り、その後は一秒ごとに一つ風船を割ることができる。
割られた時の風船の高度について最大値を得点とする。得点がもっとも小さくなるような割り方を考えるとき、このときの得点を答えよ。

制約

  • \(1 \leq N \leq 10^5\)
  • \(1 \leq H_i \leq 10^9\)
  • \(1 \leq S_i \leq 10^9\)

考え方

N が \(10^5\) までなので、風船を割る順番を決めたりして全探索するのは間に合いません。

また、貪欲的に1秒ごとにどの風船を割るのかを決めるのも難しそうです。その時の最大の高度となる風船を割ることにしても、その風船を見つけるのに\(O(N)\)だけ時間がかかり、結局 \(O(N^2)\)となって間に合いません。

この問題では発想の転換が必要です。

　「得点の最小値 X を求める」
⇔「割られた時の風船の高度は全て X 以下。このXの最小値が答え」
⇔「 風船 i は、\((X-H_i )/ S_i \) 秒以内に割ることができる。このXの最小値が答え」

と言い換えると、「割られた時の風船の高度は全て X 以下」を満たすような X の最小値を二分探索で求めることを思いつきます。

N が \(10^5\) という制約から、二分探索が使えないか疑ってみるのも解法を思いつくのに有効でしょう。

解き方

二分探索で、「割られた時の風船の高度は全て X 以下」を満たす X の最小値を二分探索で求めます。 X は 32bit の範囲では収まらないので注意しましょう。

「割られた時の風船の高度は全て X 以下」かどうかは以下の手順で判定できます。

  1. 風船 i は、\([(X-H_i )/ S_i] \) 秒以内に割ることができるので、これを全ての風船について計算しておく（\(X \le H_i \) の時は、「割られた時の風船の高度は全て \(X\) 以下」にならない）
  2. j 秒以内に割り切ることができる風船が j+1 個以内であることを確認

これの判定は、X を決めると \(O(N)\) で計算することができます。

最終的には、\(O(Nlog(max(H_i + S_i \cdot N)))\) 程度の計算量になります。

C++での実装例

#include <bits/stdc++.h>
#define LOOP(n) for (int _i = 0; _i < (n); _i++)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define RREP(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, r, n) for (int i = (r); i < (n); ++i)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;

ll N;
vector<ll> H, S;

bool f(ll mid) {  // 割られた時の風船の高度は全て mid 以下か判定
    vector<int> count(N);
    REP(i, N) {
        if (H[i] > mid) {
            return false;
        } else {
            count[min(N - 1, (mid - H[i]) / S[i])]++;
        }
    }
    REP(j, N - 1) { count[j + 1] += count[j]; }
    REP(j, N) {
        if (count[j] > j + 1) return false;
    }
    return true;
}

int main() {
    cin >> N;
    H.resize(N);
    S.resize(N);
    REP(i, N) cin >> H.at(i) >> S.at(i);

    // 二分探索
    ll l = -1, r = 1e18;
    while (r - l > 1) {
        ll mid = (r + l) / 2;
        if (f(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }

    cout << r << endl;

    return 0;
}

AtCoder最大値,二分探索,最小値