実行時間制限: 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; }
実装時間: 30分
結果的には片方を固定する全探索なのだが、「最小値を最大値とする」という考えは混乱しやすいかも。