inarizuuuushi https://blog.hatena.ne.jp/inarizuuuushi/ Sabrou-mal サブロウ丸 https://inarizuuuushi.hatenablog.com/ アルゴリズム周辺 数学 ダブリングという計算手法に感動したので、No.572 妖精の演奏 - yukicoderこの問題の解説を書こうと思います。 問題文を読むと、なるほどいかにも動的計画法チックな問題ですね、 ということで、最初は普通に以下のような定式化を行いました。 gist.github.com これで正しい答えが求まるのですが、TLE(実行時間切れ)になりました。今回 M ≦ 30, N ≤ 5*109, で最悪ケースで N >> Mなので O(NM2)のNが計算時間に特に効いてきます。なのでこのNをどうにかして小さくしたいという思いがでてきます。 そこでダブリングという手法を用います。 この手法を用いると以… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Finarizuuuushi.hatenablog.com%2Fentry%2F2017%2F10%2F21%2F081802" title="ダブリング - Sabrou-mal サブロウ丸" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/i/inarizuuuushi/20171009/20171009110601.png Hatena Blog https://hatena.blog 2017-10-21 08:18:02 rich https://inarizuuuushi.hatenablog.com/entry/2017/10/21/081802 1.0 100%