AtCoder ABC 074 C - Sugar Water (3Q, 水色, 300 点)

日頃から「まずは全探索！」という意識があれば、この手の問題は全探索でできると気づけるはず！

• 問題へのリンク

問題概要

ビーカーに対して、次の 4 種類の操作を好きな順序で好きな回数だけ実行する。

• ビーカーに g の水を入れる
• ビーカーに g の水を入れる
• ビーカーに g の砂糖を入れる
• ビーカーに g の砂糖を入れる

ただし、次の制約を満たさなければならない。

• 水 100 g あたりの砂糖の量が g 以内
• 水と砂糖の重さの総和が g 以内

これらの条件を満たしながら、濃度最大の砂糖水を作るとき、その砂糖水の水の量と砂糖の量を答えよ。

制約

• 
• 
• 
• 

考えたこと

どんな問題を解くときにも、「まずは全探索」を考えることがとても大事！

この問題も、それだけで解くことができる。操作 1, 2, 3, 4 の操作回数をそれぞれ として、4 整数の組 のとりうる値の範囲を考えてみよう。

• について： ⇔
  • なので、最悪 30 通り
• について： ⇔
  • なので、最悪 15 通り
• について： ⇔
  • なので、最悪 3000 通り
• について： ⇔
  • なので、最悪 1500 通り

ということがわかる。

これらの掛け算の通り数がある。若干多い気もするが、全探索可能な範囲だ。よって、これを全探索することで、AC がもらえる。

コード

下のコードでは、for 文を回す際に「100*A*a + 100*B*b + C*c + D*d <= F」などの枝刈り条件を入れることで、少し計算量を削減した。これで 3 ms で通っている。

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

int main() {
    int A, B, C, D, E, F;
    cin >> A >> B >> C >> D >> E >> F;

    int res_all = -1, res_sugar = -1;
    for (int a = 0; 100*A*a <= F; a++) {
        for (int b = 0; 100*A*a + 100*B*b <= F; b++) {
            for (int c = 0; 100*A*a + 100*B*b + C*c <= F; c++) {
                for (int d = 0; 100*A*a + 100*B*b + C*c + D*d <= F; d++) {
                    int water = 100*A*a + 100*B*b;
                    int sugar = C*c + D*d;
                    int all = water + sugar;

                    if (sugar * 100 > E * water || all == 0) continue;
                    if (res_all == -1 || res_sugar * all < sugar * res_all) {
                        res_all = all;
                        res_sugar = sugar;
                    }
                }
            }
        }
    }
    cout << res_all << " " << res_sugar << endl;
}