公式解説

aac003_d1 解説

この問題は大きい順にとれるものを食べていく貪欲が成り立ちます。

証明
最適解は前に詰めることができ、つまり最初から $d$ 日間ケーキを食べ続ける最適解が存在します。
小さいものが残っている状態は大きいものが残っている状態よりよく、貪欲解はある日付において可能な最も良い状態を維持します。
具体的には、貪欲解と最適解でそれぞれ小さいものとそれ以上のもののペアを作ることができれば、それらは交換が可能なため最適であることがわかります。
そのため、この貪欲は成り立つことが示せます。