SRM 458

250

弾性衝突=すり抜け
242.65

450

まず、コインの金額が決まっていたら貪欲に使うだけなので、a円以上のコインでb円を払おうとすると残りb%a円をそれ未満のコインで払うことになる
よって、
dp[i]:=一番小さいコインがi円の時に全部i円未満になるまで貪欲に払うのに必要な最小枚数
とすると、
dp[i]=min{dp[j]+Σprice%j/i | j=2i,3i,...}
となる
415.13

900

ちょっと考えると、a,b,c,dが満たすべき制約が見えてきて、bとdの関係がよく分からなかったけどb>=dなら全部いけるんじゃねとか思ってしまったorz
提出してからN=100000くらいまでa,b,c,dの組を列挙してみたところ、b>=dでもだめなパターンが存在するぽいことが判明…
しかしパターンが分からなかったorz
b-d<=(b,d)らしい
Challenge Succeeded

Challenge

450でDPしてなさそうなやつを落とそうと思ったが落とせなかったorz
-25.00

合計632.78の34位
2842 → 2840
rngさんのセットで上がった記憶がない…