10月2日のSRM練習会で、Mediumに苦戦したので備忘録的な解説を残しておきます。
・問題
重さweights[i]のケーキがvector<int> weightsで与えられ、maxCuts回自由に切ることができる。最も重いケーキと最も軽いケーキの重さの差を最小にせよ。
・方針
1.最も重いケーキを、最も軽いケーキの重さが最大化されるように切っていけばよい。
→常に等分すればよい。
→最も重いケーキの等分数をインクリメントしていく。
2.1.を満たす切り方は、「その回数の切り方の中で」最適なものである。
→より多く切ったものが最適解とは限らない。
以上が簡潔に実現されているのが、解説でも紹介されている最速提出のコードです。
LayCurseさんの提出コード