taki["blog"] = 2020 (R2)

社会人5年目(東京2年目)の日常

ABC054 D - Mixing Experiment

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


物質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