AtCoder Beginner Contest 054 D - 今日から始める競プロ日記
はじめに
AtCoderの400点を埋めたい。
今日はABC054のD問題を解く。
と言いながら結局解説を読んだので 自分なりにまとめるだけ。
D - Mixing Experiment
物質Cを作る。
物質Cは物質Aと物質BをMa : Mbの比率で混ぜることで生成できる。
ここで、N種類の薬品が与えられる。
各薬品 i は、物質Aをaiグラム、物質Bをbiグラム含み、価格はciである。
物質Cを作るのに必要な最小予算を求める。
公式解説
まず、こっちを読んだほうがいい。
https://img.atcoder.jp/abc054/editorial.pdf
私の記事では図を載せているので、その分だけ分かりやすくなっていると信じたい。
解き方
DPを使って解く。
考え方として、それぞれの薬品においてその薬品を加えた場合と加えなかった場合の重さと最小予算を記録していく。
したがって、次のような三次元配列を作る。
dp[i][ca][cb] : 1～i 番目の薬品の組み合わせ（入れるor入れない）の結果、物質Aがcaグラム、物質Bがcbグラムになり、そのときの最小予算を更新していく
このとき、最小予算を更新していくため、dpのすべての値を無限大で初期化する。 しかし、dp[0][0][0]だけは0で初期化（i=0のときは薬品はまだ一つも加えてないから重さも予算も0）。
表にあらわすと以下の図のようになる。
例として入力例1を解いてみる。
入力例1
N=3 //薬品の種類 Ma : Mb = 1 : 1 //物質Cを作るための物質Aと物質Bの比率 a1=1, b1=2, c1=1 a2=2, b2=1, c2=2 a3=3, b3=3, c3=10
dp配列において、i 番目の要素から i+1 番目の要素を更新する。
更新方法以下の二つ。
1 : 薬品 i を加えない場合
dp[i+1][ca][cb] = min(dp[i+1][ca][cb], dp[i][ca][cb])
薬品を加えないので重さは変わらず、i 番目の予算を引き継ぐかどうかだけを判断している。
2 : 薬品 i を加える場合
dp[i+1][ca+A[i]][cb+B[i]] = min(dp[i+1][ca+A[i]][cb+B[i]], dp[i][ca][cb]+C[i])
薬品を加えるため重さが変化する。 そのため、i+1 番目における変化後の重さ（ca+A[i] と cb+B[i] ）の最小予算を更新する。
この更新の様子を表で書いてみると以下の図のようになる。
まず、i=0からi=1を更新。つまり、薬品1を加える場合と加えない場合の最小予算の更新。
次に、i=1からi=2を更新。つまり、薬品2を加える場合と加えない場合の最小予算の更新。
最後に、i=2からi=3を更新。つまり、薬品3を加える場合と加えない場合の最小予算の更新。
以上の計算より、結果は以下のようになる。
この表を見ると、条件Ma : Mb = 1 : 1を満たしているなかで最小予算は 3 である（ca=3, cb=3のとき）。
このようにしてDPを用いて問題を解くことができる。
コード
コードは公式の解説PDFにのっているのでそちらを参考にする。ありがたい。
https://img.atcoder.jp/abc054/editorial.pdf
おわりに
動的計画法は少しずつ分かってきた気がするけど、 いざ問題を解こうとすると、 どう解けばいいか分からない。 まだまだ理解が足りないらしい。
