DP:ダブリング

今回は競技プログラミングに関する記事です。

初めてみたとき、アルゴリズム名から何をやってるのかよくわからなかったアルゴリズム、ダブリングのご紹介です。

ある関数  f \colon \{0,1,2,\dots,N\} \rightarrow \{0,1,2,\dots,N\} が定義されており、 \underbrace{f(f(\dots f}_{m回} (x)\dots)) の値はいくらか、というのを計算する際に効力を発揮するアルゴリズムです。

純粋に  m f を計算すると  f の計算量は  O(1) とした場合  O(m) となりますが、ダブリングを使用すると事前準備に  O(N\ log(m))、1回の計算に  O(log(m)) かかります。

そもそも、こんな形の  f って何があるんだろう、と考えると、ノード  N 個のグラフの辺上を一定のルールで動くですとか、 N + 1 を法とした mod とかがあります。

それではスクリプトをどうぞ。

class Doubling:
    def __init__(self, f, max_v, max_k):
        self.dp = [
            [None for j in range(max_v + 1)] 
            for i 
            in range(int.bit_length(max_k) + 1)
        ]
        self.dp[0] = [f(v) for v in range(max_v + 1)]
        for i in range(1, int.bit_length(max_k) + 1):
            for j in range(max_v + 1):
                self.dp[i][j] = self.dp[i-1][self.dp[i-1][j]]
                
    def solve(self, v, k):
        ans = v
        for i in range(int.bit_length(k)):
            if k & 1:
                ans = self.dp[i][ans]
            k >>= 1
        return ans

使い方は以下のような感じになります。

max_v = N
max_k = M
f = lambda x: (x + 1) % (N + 1)
doubling = Doubling(f, max_v, max_k)

print(doubling.solve(0, 10))
# => 10

まあ、この程度の問題でしたらダブリングを使わなくてもよいような感じもしますがそれはさておき。

さて、基本的な発想としては、まずは事前準備の時点で

  •  \underbrace{f(f(\dots f}_{1回} (x)\dots))
  •  \underbrace{f(f(\dots f}_{2回} (x)\dots))
  •  \underbrace{f(f(\dots f}_{4回} (x)\dots))

 \vdots

  •  \underbrace{f(f(\dots f}_{2^{i}回} (x)\dots))

 \vdots

を計算して dp テーブルに格納しておきます。この事前準備も、 2^{i} i の小さい方から、過去の計算結果を使って値を詰めていきます。おしゃれですね。

あとは、この dp テーブルの結果をもとに計算をすれば大丈夫です。

例えば  z = \underbrace{f(f(\dots f}_{5回} (x)\dots)) を求めたい場合は、

  •  y = \underbrace{f(f(\dots f}_{1回} (x)\dots))
  •  z = \underbrace{f(f(\dots f}_{4回} (y)\dots))

と2回計算をすることで(2回 dp テーブルを参照すれば)求めることができます。