足跡-sokuseki-

りかの日進月歩の記録

ABC054 D Mixing Experiment

競技プログラミング AtCoder

頑張って実装したので記事にするぞ。最近更新頻度高いし競プロ頑張ってる感がある*1。

D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder


問題概要


N種類の薬品のうちいくつかの薬品を購入する。薬品iにはタイプAの物質を a_i グラム、タイプBの物質を b_i グラム含んでおり、価格 c_i 円で売られている。
タイプAの物質とタイプBの物質の混合比が M_a : M_b となるのに必要な最小予算を求めよ。


制約

1 \le N \le 40
1 \le a_i, b_i \le 10
1 \le c_i \le 100
1 \le M_a, M_b \le 10


DP解法1


求めるものは「物質の重さの比が M_a : M_b となるのに必要な最小予算」なので、購入するそれぞれの物質の重さが最終的にわかればよい。よって、

dp[i][j][k]:=薬品 i まで見たときに、購入するタイプAの物質が合計 j グラム、タイプBの物質が合計 k グラムとなる最小費用

という配列をつくる。
j : k = M_a : M_b となるdp[n][j][k]の最小値が求める最小費用。

計算量は O(N^3 (max( a_i, b_i ))^2 ) 。


Submission #1123367 - AtCoder Beginner Contest 054 | AtCoder


DP解法2


さっきのDP解法よりさらに計算量を落とすことができる。

(タイプAの物質の合計の重さ)：(タイプBの物質の合計の重さ)＝ M_a： M_b

となれば良いので、

(タイプAの物質の合計の重さ) * M_b - (タイプBの物質の合計の重さ) * M_a = 0

となる最小費用をもとめればよい。よって、

dp[i][j]:=薬品 i まで見たときに、「購入するタイプAの物質の合計の重さと M_b の積」と「購入するタイプBの物質の合計の重さと M_a の積」の差が j のときの最小費用

という配列を作り、dp[n][0]が答えとなる(ただし、このままだとjは負の値をとることがあるので、jの値はずらす必要がある)。

計算量は O(N^2 max( a_i , b_i ) max( M_a, M_b )) *2。


Submission #1121081 - AtCoder Beginner Contest 054 | AtCoder




DP解法3


もう一つ別の解法があるのを見つけたので紹介だけ(参考サイト：ABC054-D「Mixing Experiment」 | クリエイティヴなヴログ)。
計算量はさっきのDP解法2と変わらないけど、やりかたが違う。

各薬品 i について、

d[i]:= a_i * M_b - b_i * M_a

を最初に求めておく。そのあと、

①d[i]=0となる c_i の最小値を求める
②d[i]<0となるものとd[i]>0となるものをいくつか選び、和が0になるものの最小予算を求める(ここでDPを使う)

①と②のうち小さいほうが答えとなる(詳しい解き方はリンク先をみてください)。



半分全列挙


半分全列挙は昔に一度だけやったことがあるけど*3、復習しないので覚えてなかった(ので昔のコードを見ながら思い出しつつやった)。

半分全列挙は、まず半分にわけて、それぞれでありえる組み合わせを全列挙して、うまくmergeして答えを求める方法。名前そのまま。
計算量は、半分にわけて全列挙するところが O( 2^{ \frac{N}{2}} ) で、mergeするところが O( \frac{N}{2}) なので全体で O( \frac{N}{2} \times 2^{ \frac{N}{2}}) *4。


Submission #1128677 - AtCoder Beginner Contest 054 | AtCoder


感想


コンテスト中に通したかった……(そもそも全探でしようとしてたのでダメ)

ひとつの問題でいろいろな解き方ができるのは本当におもしろいし楽しいなあ。

*1:と書き始めた当初は思っていたが、記事が完成するのに1週間近くかかったのでダメ

*2:配列の大きさで考えると O(N^2 max( a_i , b_i ) ( M_a + M_b ) ) になる

*3:C: 無駄なものが嫌いな人 - AtCoder Regular Contest 017 | AtCoder

*4:この書き方だと某警察につかまりそう。 O(N \times 2^{ \frac{N}{2} }) が正しいのだと思うけど、それでは N=40 でうまくいくことがわからないし…。