htkb-proconの日記

初心者がPythonで問題解いた記録

ABC054-D DP

D - Mixing Experiment

DPやるだけの400点問題なんだけど今更こんなのでハマってしまったので忘れないように記す。

2種類の物質がa:bで混じっているc円の薬がN個あるので、これを好きなように混ぜてなるべく安く指定の比率を実現したいという問題で、制約もゆるいのでaの物質とbの物質の量でDPするんだけど、dp[i番目まで見た][aの物質の量][bの物質の量]と3次元DPテーブルを立てるところを、dp[aの物質の量][bの物質の量]と2次元DPにしてしまった。

WA: Submission #1353922 - AtCoder Beginner Contest 054 | AtCoder

変なWA出た時点で解説見たんだけど、i番目までってのを覚えとかなくてもカウント漏れはしないよなぁ……?としばらく何が悪いのか気付けなかった。カウント漏れは確かにしないはずだけど、

N=3
1:2の薬 1円
2:1の薬 2円
3:3の薬 1円

というテストケースがあった場合、2次元DPだと

dp[0][0] = 0
dp[0][0] = 0, dp[1][2] = 1
dp[0][0] = 0, dp[2][1] = 2, dp[1][2] = 1, dp[3][3] = 3

と動いたあと、最後の薬を考慮するときに

dp[0+3][0+3] = min(dp[0][0]+1, dp[3][3]) = 1
dp[3+3][3+3] = min(dp[3][3]+1, dp[6][6]) = 2
                   ^^^^^^^^
            3だったのに1に書き換わってる!!

というふうに、他のケースの遷移で値が上書きされるようなことが起こりうるはず。これが3次元DPならば薬を足す前の値はdp[i-1]から取るし、薬を足した後の値はdp[i]に入れるのでぶつからないわけ。考え方が誤っている証明が浮かばなかったので無駄に悩んでしまったけど、DPでは何番目までを考慮したかをちゃんと状態として持ちましょうという自明オブ自明な話でした。

AC: Submission #1354004 - AtCoder Beginner Contest 054 | AtCoder


追記

量を増やした時に衝突する可能性があるのだから多い方から見てけば衝突を避けられるのは自明でした。結局どう回ってるのかしっかり把握せずにコード書いてるのでバグったりするわけですはい。

Submission #1355632 - AtCoder Beginner Contest 054 | AtCoder

少し早くなってメモリ使用量が1/8くらいになった!アドバイスありがとうございます🙇