[AtCoder] ABC 144 E – Gluttony

2019年10月28日

問題

方針

最適な食べ物の配置

証明ができなかったので、予想を立てて考えます。おそらく、修行前の最適なコストは、次のようになります。配列 \( A, F\) を

\[ A_1 \geq A_2 \geq \cdots \geq A_N \]

\[F_1 \leq F_2 \leq \cdots \leq F_N\]

と整列させます。このときのコストを、\( c \) とすると、

\[ c = \max A_iF_i \ ( 1 \leq i \leq N)\]

となります。

二分探索

成績 \( x \) を二分探索によって求めます。また、以下の手法も証明ができませんでした。上記の食べ物の配置のままで、修行を行います。\[A_iF_i > x\] を満たす \( i \) について、

\[ \lceil  \dfrac{A_iF_i – x}{F_i} \rceil\]

回の修行を行うとします。この修行回数の累積和が \( K \) 以下であれば、その \( x \) の成績は達成可能です。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll N;
    ll K;
    cin >> N >> K;
    vector<ll> A(N), F(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < N; i++) {
        cin >> F[i];
    }
    sort(A.begin(), A.end(), greater<ll>());
    sort(F.begin(), F.end());
    ll cost = 0;
    ll ans = F[N - 1] * A[0];
    ll l = -1;
    ll r = ans + 1;
    ll m;

    while (r - l > 1) {
        m = l + (r - l) / 2;
        cost = 0;
        for (int i = 0; i < N; i++) {
            if (A[i] * F[i] > m) {
                cost += (A[i] * F[i] - m + F[i] - 1) / F[i];
            }
        }
        if (cost <= K) {
            ans = m;
            r = m;
        } else {
            l = m;
        }
    }
    cout << ans << "\n";
    return 0;
}

感想

解説を見ましたがよく分かりませんでした。