AtCoder Regular Contest 021 C - 増築王高橋君

問題

arc021.contest.atcoder.jp

解法

まず浮かぶのは, priority_queue に値を突っ込んでいく形でコストが小さい順に貪欲にやることです。ただ, K <= 10^8 なので, これだと間に合いません。

そこで, K 回の増築の中で, 最もコストのかかる増築のコスト x について二分探索しましょう。コスト x 以下で行える増築が K 回以上あれば, 最大コストは x 以下であるとわかります。
x の値がわかったら, 合計コストは,

• x 未満のコストのすべての増築を行う
• コストが x の増築は, 増築回数が K になるまで行う

の計算によって得ることが出来ます。

…と発想はまぁ普通なんですが,

• 二分探索の範囲をでかくし過ぎると overflow する
• long long だと overflow する(最大で (10^3 + 10^3 * 10^8) * 10^8 = 10^19 となるため)

ことに注意しましょう…

typedef unsigned long long ll;

const int MAXN = 100100;
ll A[MAXN], D[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    ll K;
    cin >> K;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i] >> D[i];
    ll low = 0, high = 1e12;
    while (high-low > 1) {
        ll med = (high+low)/2;
        ll cnt = 0;
        for (int i = 0; i < N; i++) {
            if (med < A[i]) continue;
            cnt += (med-A[i])/D[i]+1;
        }
        if (cnt >= K) high = med;
        else low = med;
    }
    ll ans = 0, cnt = 0;
    for (int i = 0; i < N; i++) {
        if (high < A[i]) continue;
        ll num = (high-A[i])/D[i]+1;
        cnt += num;
        ans += (A[i]+A[i]+(num-1)*D[i]) * num / 2;
    }
    ans -= high*(cnt-K);
    cout << ans << endl;
    return 0;
}