問題概要

$N$ 体のモンスターがいて、それぞれ質量は $A_{i}$ 、魔力は $B_{i}$ である。

また、 $M$ 体のお助けモンスターがいて、それぞれ質量は $C_{i}$ 、魔力は $D_{i}$ である。

今、これら $N + M$ 体のモンスターからちょうど 5 体を選んで合体させる。ただし、お助けモンスターは最大で 1 体までしか合体に用いることはできない。合体に用いたモンスターについての (魔力の総和) を (質量の総和) で割った値の最大値を求めよ。

制約

$5 \le N \le 1000$
$1 \le M \le 100$

考えたこと

魔力の重み付き平均値を最大化したいという問題だ。この手の問題は「二分探索」で解けると相場は決まっている。(魔力の総和) / (質量の総和) を $x$ 以上にできるかどうかを判定する問題を解くことにしよう。

合体に用いるモンスターの魔力を $p_{1}, p_{2}, p_{3}, p_{4}, p_{5}$ 、質量を $m_{1}, m_{2}, m_{3}, m_{4}, m_{5}$ とすると、条件は

$\displaystyle \frac{p_{1} + p_{2} + p_{3} + p_{4} + p_{5}}{m_{1} + m_{2} + m_{3} + m_{4} + m_{5}} \ge x$
⇔ $\displaystyle (p_{1} - xm_{1}) + (p_{2} - xm_{2}) + (p_{3} - xm_{3}) + (p_{4} - xm_{4}) + (p_{5} - xm_{5}) \ge x$

と表せる。左辺を最大化したいということになる。これは、モンスターのうち、 $(魔力) - x \times (質量)$ が大きい順に 5 体選べばよい。ただし、お助けモンスターについては 2 体以上は選ばないこととする。

よって、判定問題が $O(N \log N + M \log M)$ の計算量で解けた。二分探索のイテレーション回数は 100 回程度で十分であり、十分間に合う。

コード

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

const double INF = 1LL<<30;
int main() {
    int N, M;
    cin >> N >> M;
    vector<double> A(N), B(N), C(M), D(M);
    for (int i = 0; i < N; ++i) cin >> A[i] >> B[i];
    for (int i = 0; i < M; ++i) cin >> C[i] >> D[i];
    
    double low = 0, high = INF;
    for (int _ = 0; _ < 100; ++_) {
        double x = (low + high) / 2;
        
        // モンスター、お助けモンスターそれぞれについて、(魔力) - x × (質量) を大きい順に並べる
        vector<double> monster(N), otasuke(M);
        for (int i = 0; i < N; ++i) monster[i] = B[i] - x * A[i];
        for (int i = 0; i < M; ++i) otasuke[i] = D[i] - x * C[i];
        sort(monster.begin(), monster.end(), greater<double>());
        sort(otasuke.begin(), otasuke.end(), greater<double>());
        
        // お助けモンスターを使わない場合と、1 体使う場合
        double tmp1 = monster[0] + monster[1] + monster[2] + monster[3] + monster[4];
        double tmp2 = otasuke[0] + monster[0] + monster[1] + monster[2] + monster[3];
        if (max(tmp1, tmp2) >= 0) low = x;
        else high = x;
    }
    cout << fixed << setprecision(10) << low << endl;
}

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

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

第 1 回 PAST M - おまかせ

問題概要

制約

考えたこと

コード