ABC054 D - Mixing Experiment

こういうページを参考にしつつ，DP精進をしています．

• 競技プログラミングにおける動的計画法問題まとめ https://www.hamayanhamayan.com/entry/2017/02/27/021246

---

物質i (それぞれai, biグラムの物質を含む）を選んで，最小コストで比率Ma:Mbを達成するような動的計画法です．

first attempt

3次元DPを考えて，dp[i][j][k]としてi番目以下の物質を使って比率j:kを達成するときの最小コストを考えます．しかし比率にするとイマイチ漸化式が思いつかなかった（整数で保存できない）ので，ここは選択した量の和を使うことを思いつきました．

dp[i][j][k]: i番目以下で物質Aをjグラム，物質Bをkグラム投入した際の最小コスト

比率Ma:Mbと個数Nから，だいたいN×Maぐらいのテーブルを作れば良いので，問題サイズだとセーフっぽい気がします．

コネコネして最初に作ったDP式はこんな実装でした（貰うDP）．つまり(i, j, k)のコストは

• すでに計算済みのコスト dp[i][j][k]
• i番目を使わないコスト (dp[i - 1][j][k])
• i番目を使った際に今の加えた量(j ,k)になる場合のコスト dp[i - 1][j - ai][k - bi] + ci

という気持ちの実装です（間違い）．ACコードとだいたい同じでしたが，もうひと頑張り，ぐらいでしょうか（WAです）．

for i in range(1, N + 1):
    ai, bi, ci = la[i - 1], lb[i - 1], lc[i - 1]
    for j in range(sumA + 1):
        for k in range(sumB + 1):
            if j - ai >= 0 and k - bi >= 0:
                dp[i][j][k] = min(dp[i - 1][j - ai][k - bi] + ci, dp[i][j][k], dp[i - 1][j][k])

ans = Inf
for j in range(1, sumA + 1):
    for k in range(1, sumB + 1):
        if j / k == Ma / Mb:
            ans = min(ans, dp[N][j][k])
if ans == Inf:
    print(-1)
else:
    print(ans)

解説→ACコード

• 配るDP部分です．もう少し直したらWAコードもAC出来るかもしれないですね．

for i in range(N):
    ai, bi, ci = la[i], lb[i], lc[i]
    for j in range(sumA + 1):
        for k in range(sumB + 1):
            if dp[i][j][k] == Inf:
                continue
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])
            dp[i+1][j+ai][k+bi] = min(dp[i+1][j+ai][k+bi], dp[i][j][k]+ci)

追記

• 貰うDPも条件を直したら通りました

Submission #13009073 - AtCoder Beginner Contest 054 | AtCoder