【AtCoder】ABC 338 C - Leftover Recipes | 茶コーダーが解くAtCoder

atcoder.jp

実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 513

問題概要

いま、 種類の材料があり、材料 は グラムある。これらの材料を使って2種類の料理 A, B を作ることを考える。料理 A には一人分に各材料が グラム必要で、料理 B には一人分に各材料が グラム必要である。このとき、最大で計何人分の料理を作ることができるかを求めよ。

制約

• 入力はすべて整数。
• 
• 
• 

考察

料理 A, B をそれぞれ 人分作ることにする。単純に考えると を全探索して、すべての に対し を満たすかどうかを判定していけばよい。だが、2つの料理は最大で 人分作れる (例えば、 のときなど) ので、これでは間に合わない。

ここで、 のいずれかを固定したときに、もう一方は即座に決まることに注目してみよう。

例えば、 と固定したとき、各 に対して残りの材料 は であり、このとき最大で 人分の料理を作ることができる。

このようにして求めた の最小値が、結果的に作ることができる料理 B の最大値 (コード中のmax_b) である (これより小さい はすべての に対し を満たす) 。

また、 についても作ることができる料理 A の最大値 (コード中のmax_a) を求めておく。

最終的な答えは、 で走査したときの の最大値となる。

コード

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<int> Q(N), A(N), B(N);
    rep(i, 0, N) cin >> Q[i];
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    int max_a = INF;
    rep(i, 0, N) if (A[i] > 0) chmin(max_a, Q[i] / A[i]);

    int ans = 0;
    rep(a, 0, max_a + 1)
    {
        int max_b = INF;
        rep(i, 0, N)
        {
            int rest = Q[i] - A[i] * a;

            if (B[i] > 0)
                chmin(max_b, rest / B[i]);
        }
        chmax(ans, a + max_b);
    }

    cout << ans << endl;
}

atcoder.jp

実装時間: 30分

結果的には片方を固定する全探索なのだが、「最小値を最大値とする」という考えは混乱しやすいかも。