ダブリング

ダブリングという計算手法に感動したので、
No.572 妖精の演奏 - yukicoderこの問題の解説を書こうと思います。


問題文を読むと、なるほどいかにも動的計画法チックな問題ですね、
ということで、最初は普通に以下のような定式化を行いました。

gist.github.com
これで正しい答えが求まるのですが、TLE(実行時間切れ)になりました。今回 M ≦ 30, N ≤ 5*10⁹, で最悪ケースで N >> Mなので
O(NM²)のNが計算時間に特に効いてきます。なのでこのNをどうにかして小さくしたいという思いがでてきます。


そこでダブリングという手法を用います。
この手法を用いると以下のように定式化できます。



つまりすべての z (1 ≤ z ≤ N)に対して計算するのではなく、
1 ≤ 2^z ≤ Nをみたすzだけ計算するのがミソなんですね。
そのかわり始点と終点の両方を指定する必要がありますが。

そして、計算したDPを用いて以下を計算します。


最終的には2回動的計画法を実行することになります。
計算量の比較についてですが, 今 N >> M² なので NM² >> M³ logN となり、こちらの手法の方が高速に計算できることが分かります。
gist.github.com

二進展開の部分は以前書いたこの記事の後半の部分を使用しました。



動的計画法は奥が深くて面白いですね。