nanikaka https://blog.hatena.ne.jp/nanikaka/ nanikakaのAOJ航海日誌 https://nanikaka.hatenadiary.org/ AOJ Volume2 問題リンク Bara-Bara Manju 解法 深さ優先探索+枝刈りが方針です。 何をどう深さ優先探索したのかという話になりますが、ずばり、「10の作り方」です。 10を和で表現する方法は調べてみると41通りあります。この10の作り方それぞれに番号を振り、k番の10の作り方を使って10を作る個数を探索します。枝刈りのために、残っている整数の総和をSとします。すると、どんなに頑張っても残りS/10個しかおまんじゅうを詰めれません。これを使って解が更新できるかをチェックします。 まだ時間が足りません。そこで、(1, 9)(2, 8)(3, 7)(4, 6)(5, 5)というまんじゅうの詰め方を作… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnanikaka.hatenadiary.org%2Fentry%2F20120715%2F1342343102" title="AOJ0246 Bara-Bara Manju - nanikakaのAOJ航海日誌" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2012-07-15 18:05:02 rich https://nanikaka.hatenadiary.org/entry/20120715/1342343102 1.0 100%