yutasの競技プログラミング勉強帖

競技プログラミングの問題についての解説記事を主に書いています。

C - Leftover Recipes / AtCoder Beginner Contest 338

ABC338 AtCoder C++ AtCoder Beginner Contest 300点 競技プログラミング

問題

冷蔵庫に n 種類の材料があり、これらは材料 1, \, \cdots , \, n と番号が付けられている。 材料 i は {q}_{i} グラムある。

ここで、2種類の料理が作れる。 料理Aは、1人分を作るのに各材料 i が {a}_{i} グラム必要であり、料理Bは、1人分を作るのに {b}_{i} グラム必要である。 また、どちらも整数人分しか作ることができない。

このとき、冷蔵庫にある材料のみを使って、最大で合計何人分の料理を作れるか求めよ。

入力

まず最初の1行目に、整数 n が与えられる。

次の1行には、 n 個の整数 {q}_{1}, \, {q}_{2}, \, \cdots , \, {q}_{n} が空白区切りで与えられる。

次の1行には、 n 個の整数 {a}_{1}, \, {a}_{2}, \, \cdots , \, {a}_{n} が空白区切りで与えられる。

次の1行には、 n 個の整数 {b}_{1}, \, {b}_{2}, \, \cdots , \, {b}_{n} が空白区切りで与えられる。

条件

  • 実行時間制限: 2s
  • メモリ制限: 1024MB
  • 1 \leq n \leq 10
  • 1 \leq {q}_{i} \leq {10}^{6}
  • 0 \leq {a}_{i} \leq {10}^{6}
    • {a}_{i} \geq 1 であるような i が存在する。
  • 0 \leq {b}_{i} \leq {10}^{6}
    • {b}_{i} \geq 1 であるような i が存在する。

出力

最大で合計 s 人分の料理を作れるとき、1行で整数 s を出力すること。

解法

まず、料理Bを作らずに料理Aのみを作る場合について考えます。 このとき、料理Aを最大で何人分作れるのか、ということを考えます。

これは、 {a}_{i} \ne 0 である各材料に対して \displaystyle \left\lfloor \frac{ {q}_{i} }{ {a}_{i} } \right\rfloor の値を求めていき、その中の最小値が答えとなります。 というのも、すべての材料が揃っていないと料理を作ることができないためです。

従って、この値を {s}_{a} として、以下料理Bも作る場合について考えます。

ここで、料理Aを i 人分作るときについて考えます。（ただし、 0 \leq i \leq {s}_{a} とします。）

このとき、材料 j は ({q}_{j} - i \cdot {a}_{j}) だけ余っています。 そのため、料理Bを最大で何人分つくれるのか、ということについては先程と同様に、 {b}_{j} \ne 0 である各材料に対して、 \displaystyle \left\lfloor \frac{{q}_{j} - i \cdot {a}_{j}}{{b}_{j}} \right\rfloor の値を求めていき、その中の最小値が答えとなります。

このようにして、料理Aを i 人分作るときの料理Bを作れる最大値を求めていき、その和の最大値を i = 0, \, 1, \, \cdots , \, {s}_{a} の範囲で求めることによって、この問題の答えが得られます。

計算量については、料理Aを最大で {s}_{a} 人分作れるとしたときに、 O({s}_{a} n) で求めることができます。 この問題では n \leq 10 であり、 \displaystyle {s}_{a} \leq \frac{{q}_{i}}{{a}_{i}} \leq {10}^{6} であるので、これは実行時間制限に十分間に合うと言えます。

ソースコード

まず、料理Aを何人分作るのかということを引数として、最終的に作ることのできる人数の合計値を返す関数 solve() を以下のように実装しました。

int n;
ll q[15], a[15], b[15];

ll solve(ll a_cnt) { // a_cnt は料理Aを作る人数を表す
  ll b_cnt = 1e9; // b_cnt は料理Bを作る人数を表す

  // i = 1, ..., n の順に、b_cnt の値を更新していく
  for (int i = 1; i <= n; i++) {
    ll rest = q[i] - a[i] * a_cnt; // 材料 i の残りの量を表す rest

    if (b[i] == 0) {
      // b[i] = 0 のときは考慮する必要がない
      continue;
    }
    b_cnt = min(b_cnt, rest / b[i]); // b_cnt の値を更新する
  }

  return a_cnt + b_cnt; // 最終的に a_cnt と b_cnt の和を返す
}

この solve() 関数が実装された状態で、 main() 関数の中に、答えを出力する部分を直接実装しました。

int n;
ll q[15], a[15], b[15];

int main() {
  // 値の入力
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> q[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }

  ll a_max = 1e9; // 料理Aを作れる人数の最大値を表す a_max
  for (int i = 1; i <= n; i++) {
    if (a[i] == 0) {
      // a[i] = 0 のときは考慮する必要はない
      continue;
    }
    a_max = min(a_max, q[i] / a[i]); // a_max の値を更新する
  }

  ll ans = 0; // 最終的な答えを表す ans

  // i = 0, ..., a_max について、作れる料理の個数を計算して ans を更新する
  for (ll i = 0; i <= a_max; i++) {
    ans = max(ans, solve(i));
  }
  cout << ans << endl;

  return 0;
}