AtCoder Beginner Contest 023 D - 射撃王

問題

abc023.contest.atcoder.jp

日.

解法

二分探索による最大値の最小化問題です.
:=(全ての風船を以下で撃ち落とすことができる)とします. これを満たすための最良の戦略は, この高さに達するまでの時間が短い風船から貪欲に撃ち落とすことです. この戦略に従ってが成立するかどうかを調べます. あとは二分探索です.

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

typedef long long ll;
typedef pair<ll, int> P;

const ll kINF = 1LL << 50;
const int kMAX_N = 100010;

int N;
ll H[kMAX_N], S[kMAX_N];

bool C(ll x) {
    vector<P> y(N);
    for (int i = 0; i < N; i++) {
        y[i] = make_pair((x - H[i]) / S[i], i);
    }
    sort(y.begin(), y.end());

    for (int i = 0; i < N; i++) {
        P baloon = y[i];
        if (H[baloon.second] + S[baloon.second] * i > x) return false;
    }
    return true;
}

void Solve() {
    ll lb = 0, ub = kINF;
    while (ub - lb > 1) {
        ll mid = (ub + lb) / 2;
        if (C(mid)) {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    cout << ub << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N;

    for (int i = 0; i < N; i++) {
        cin >> H[i] >> S[i];
    }

    Solve();

    return 0;
}

感想

実行時間がきつい.