けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 054 D - Mixing Experiment (400 点)

なんだろ

問題へのリンク

問題概要

 N 個の薬品があって、それぞれ成分 A, B を  a_i, b_i グラムずつ含んでいる (すべて整数値)。

これらのうちのいくつかを選んで混ぜ合わせることで、成分 A, B の比がちょうど  M_A :  M_B となるようにしたい。

そのようなことが可能となる薬品の組合せのうち、質量の総和の最小値を求めよ。

制約

  •  1 \le N \le 40
  •  1 \le a_i, b_i, M_A, M_B \le 10
  •  1 \le c_i \le 100

解法 1: ナップサック問題

とりあえず、全探索しようと思うと  O(2^{N}) 通りになる。今回  N がちょっと小さいとはいえ間に合わない。

でもこういう風に  O(2^{N}) 通りという状況は、

  • 部分和問題みたいな DP
  • 半分全列挙

を疑いたくなる状況ではある。今回はどちらでもできる。部分和問題っぽくやってみる。

  • dp[現在の個数][現在の重さ] := 価値の最大値だったり最小値だったり

という形が典型的だが、今回は成分 A, B の二つがあるので

  • dp[現在の個数][現在の成分 A の重さ][現在の成分 B の重さ] := 価格の最小値 (実現できないなら INF)

としてみる。こういう DP テーブルを作っておいて、A の重さと B の重さの比がちょうど  M_A :  M_B になるところを調べれば OK。

#include <iostream>
#include <vector>
using namespace std;
void chmin(long long &a, long long b) { if (a > b) a = b; }
const long long INF = 1LL<<60;

int N;
long long ma, mb;
vector<long long> a, b, c;

long long dp[51][510][510];

int main() {
    cin >> N >> ma >> mb;
    a.resize(N); b.resize(N); c.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i] >> b[i] >> c[i];
    
    for (int i = 0; i < 51; ++i) for (int j = 0; j < 510; ++j) for (int k = 0; k < 510; ++k) dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    for (int i = 0; i < N; ++i) {
        for (int wa = 0; wa < 500; ++wa) {
            for (int wb = 0; wb < 500; ++wb) {
                if (dp[i][wa][wb] >= INF) continue;
                
                // 使わない
                chmin(dp[i+1][wa][wb], dp[i][wa][wb]);

                // 使う
                chmin(dp[i+1][wa+a[i]][wb+b[i]], dp[i][wa][wb] + c[i]);
            }
        }
    }
    long long res = INF;
    for (int wa = 1; wa < 500; ++wa) {
        for (int wb = 1; wb < 500; ++wb) {
            if (wa * mb != wb * ma) continue;
            chmin(res, dp[N][wa][wb]);
        }
    }
    if (res < INF) cout << res << endl;
    else cout << -1 << endl;
}

解法 2: 半分全列挙

ちょっとイメージしづらいけど、半分全列挙でもできる。