betrue12 https://blog.hatena.ne.jp/betrue12/ ARMERIA https://betrue12.hateblo.jp/ プログラミング 競技プログラミング AOJ お題箱より。 Aizu Online Judge Arena 解法 答えとなる金額の払い方の必要条件を考える ある金額 について貪欲な払い方よりも真に枚数が少ない払い方が存在することを、単に「金額 は条件を満たす」と書くことにします。そして条件を満たす最小の金額（答え）が存在すると仮定して、それを 円と表記します。 答えとなる 円の払い方について必要条件を考えてみると、実は意外と絞れることに気づきます。まず、 円の貪欲な払い方は、 円硬貨を必ず含む ということが言えます。つまり必ず であるということです。もしそうでない場合使える硬貨は 円と 円だけになり、これでは貪欲が必ず最適になるからです。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbetrue12.hateblo.jp%2Fentry%2F2019%2F08%2F03%2F183224" title="HUPC2019 Day1 D: 貪欲が最適？ - ARMERIA" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-08-03 18:32:24 rich https://betrue12.hateblo.jp/entry/2019/08/03/183224 1.0 100%