ABC054 D Mixing Experiment

D Mixing Experiment

Submission #2508458 - AtCoder Beginner Contest 054

所見

二次元DPの表を薬品の回数だけ更新することを思いついたが、解説の三次元DPではやっていることは同じようだ。(多分)三次元になると脳内での構成が不可能になるのでなんとかしたい。

問題概要

N種類の薬品が与えられる。薬品はそれぞれ薬品aと薬品bからなり、i番目の薬品はaをaiグラム、bをbiグラム含み、価格はciである。MaとMbが与えられるとき、含む薬品の比ををa:b=Ma:Mbにしたい。そのようにできる組み合わせのうち、価格の和が最小のものを求めよ。

取った方針

dp[i][j]に、薬品aがiグラム、bがjグラム含む際の最小価格を入れることとする。
すべての薬品について、すべての価格が定義されているセルに対しその薬品を混ぜた時のコストを表に新たに書き込み、それを更新操作とする。
式にすると以下のようになる。

dp[i + a][j + b] = min(dp[i][j] + c, dp[i + a][j + b]);

この更新操作をすべての薬品について行うと、実現可能なaとbの重さの組み合わせにおいて、dp[a][b]にその最安値が入るので、a/b==Ma/Mbなるa,bについて価格の最低値を出力すればよい。
ただし、a/bはdouble値になるので、誤差を許容して比較する必要がある。

int ans = INF;
for (int i = 0; i < 500; i++) {
    for (int j = 0; j < 500; j++) {
        double target = (double)Ma / (double)Mb;
        double now = (double)i / (double)j;
        if (abs(target - now) < 0.000001 && dp[i][j] < ans) {
            ans = dp[i][j];
        }

    }
}

正しい方針(解説に載っている方針)

dp[i][ca][cb] を 1-i(よくわからないが、「i番目まで」、の誤植のような気がする)番目までの薬品の組み合わせのうち、物質Aをcaグラム、Bをcbグラム含む溶液の最小コスト とする。
最初はdp[0][0][0]を0グラムで初期化し、私の方針と同様にdp[n]の表からdp[n+1]の表を生成する。
解説のプログラムでは、「i番目の薬品を使わない場合」と「使う場合」の両方の更新を行っているが、私の方針の場合は既に「i番目の薬品を使わない場合」の値がdp[ca][cb]に入っているので、使う場合のみ更新処理を行っている部分が違う。

得られた知見

・表を用いたDP
・使う物品の数を一つずつ増やしていくナップザック感覚のDP
・dp[i][j][k]は table[j][k] なる二次元配列がi個あるという感覚
・一つの表が一つの状態を表し、遷移は次の表に書き込むという型のDP
・もっと多次元化することもできそう(頭がフットーしそう)

解くのに必要な要素

・表を更新するタイプのDP

周辺調査によって得られた知見

特になし