AOJ 1603 500-yen Saving (ICPC Domestic 2015 D)
問題を見てすぐにDPっぽいということが分かる。使用した最小金額を値として持つということが自然なので、すぐに思いつく解法としては[店の数]×[500円の数]×[小銭]が考えられる。なので通るかと思い、実装した。色々とバグらせてしまい、この時点で50分くらいかかっていた。
まずMLEを受けた。dp表を更新するものに直したらTLEを受けた。AOJで制限が8秒だったが13秒くらいだった。しかし定数倍高速化できそうな要素もないので（だいぶ色々と試してから）諦めて講評を見た。講評によれば想定解の1個目が僕の解法で、2個目は状態として500円の数と使用した金額の組みを状態として持つというものだった。確かに、問題を自然によめばこの解法になる気がする。無意識のうちに見たことがあるDPの解法に落とし込もうとしてしまったかもしれない。
正直、1個目の解法ができたので満足ではあるが、1個目でもかなりバグらせてしまったので反省したい。そろそろリハビリという言い訳も効かなくなってきたので、一問一問を丁寧に解くようにしたい。
