anta1 https://blog.hatena.ne.jp/anta1/ antaの競技プログラミング練習日記 https://anta1.hatenadiary.org/ SRM DP 実装のアイデア 問題 Editorial 問題 箱を2*2*heightに積む。 それぞれの箱は独立に、0.5の確率でダイナマイトが入っていて、そうでなければ空である。 「ダイナマイトクラスター」とはダイナマイトの入った箱の集合で、連結なものである(面でのみ接しているとみなす)。 サイズがdangerousClusterSize以上であるダイナマイトクラスターを含む確率を求めよ 1 1 解答 DP。まず、2*2なので、各段ごとに最大でも2つの独立のクラスターしか関係しないことに注意する。 なので(高さ * 前の段の状態bitmask * 前の段のクラスターサイズ1 * 前の段のクラスターサイズ2)というふうな… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fanta1.hatenadiary.org%2Fentry%2F20130227%2F1361908945" title="SRM 297 DIV1 Hard DynamiteBoxes - antaの競技プログラミング練習日記" 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 2013-02-27 05:02:25 rich https://anta1.hatenadiary.org/entry/20130227/1361908945 1.0 100%