moistx https://blog.hatena.ne.jp/moistx/ Logfiles https://logfiles.hatenablog.com/ AOJ 解答 K = 30 までで O(2^K) なので、多少枝刈りすれば通るだろうと思っていたが TLE がなかなか取れなかった。決め手は solve() 関数内の 2行目の枝刈り。条件式を満たすとき今の確率を P倍 と (1-P)倍 に分割する必要がなくなる。コメントアウトしてある条件式は、枝刈りで苦悩した軌跡。確率が 0 に近くなれば弾くという考えばかりが頭を走っていた。 #include <iostream> #include <algorithm> #include <vector> #include <cstdio> #include <cmath> using namespace std… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Flogfiles.hatenablog.com%2Fentry%2F20140909%2F1410270581" title="AOJ2301 Sleeping Time - Logfiles" 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 2014-09-09 22:49:41 rich https://logfiles.hatenablog.com/entry/20140909/1410270581 1.0 100%