[Codeforces] Educational Codeforces Round 94 (Rated for Div. 2) B. RPG Protagonist

2020年9月2日2020年12月13日

問題

問題の解釈

許容重量 \( p \) のリュック1と許容重量 \( f \) のリュック2があります。重さが \( s \) と \( w \) のモノがそれぞれ \( a \) 個と \( b \) 個あるとき、二つのリュックに入れられるモノの最大数を求めます。

問題文では \( a = cnt_s, b = cnt_w \) となっています。

方針

\( p < f \)、\( s < w \) としても一般性を失わないので、この条件下で考えます。まず初めに、リュック1 に重さ \( s \) の剣を入れられる個数 \( x_1 \) は最大で、

\[ x_1 = \min(a, \left \lfloor \dfrac{p}{s} \right \rfloor)\]

です。次に、リュック1に \( i \ (0 \leq i \leq x) \) 個の剣を入れた時、リュック1に入れられる重さ \( w \) の斧の個数 \( y_1 \) は、

\[ y_1 = \min(b, \left \lfloor \dfrac{p – is}{w} \right \rfloor)\]

となります。このとき、リュック2に剣を先に可能な限り入れ、斧を最後に入れることでリュックに入る剣と斧の個数が分かります。

したがって、リュック1に入れる剣の個数について全探索します。制約にテストケースの剣と斧の総数は \( 2 \times 10^5 \) 以下なので、計算量は大丈夫です。

コード

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

ll max_v = 0;
ll solve(ll p, ll f, ll a, ll b, ll s, ll w) {
    
    if (p > f) {
        swap(p, f);
    }
    if (s > w) {
        swap(s, w);
        swap(a, b);
    }
    ll max_v = 0;
    ll v = min(a, p / s);
    for (int i = 0; i <= v; i++) {
        ll x2 = min(a - i, f / s);
        ll y1 = min(b, (p - i * s) / w);
        ll y2 = min(b - y1, (f - x2 * s) / w);
        max_v = max(max_v, i + x2 + y1 + y2);
    }
    return max_v;
}

int main() {
    int t;
    cin >> t;
    ll p, f, cnt_s, cnt_w, s, w;
    ll ans[t];
    for (int i = 0; i < t; i++) {
        cin >> p >> f >> cnt_s >> cnt_w >> s >> w;
        ans[i] = solve(p, f, cnt_s, cnt_w, s, w);
    }
    for (ll i : ans) {
        cout << i << "\n";
    }
    return 0;
}