半分にするテク

3^n DP でループ回数を半分にするテク

「$3^n$ $\mathrm{DP}$ でループ回数を半分にするテク」、略して「半分にするテク」について書きます。

半分って何？

$3^n$ $\mathrm{DP}$ と呼ばれるアルゴリズムがありますね。部分集合を列挙して処理するやつです。普通にやるとループが $3^n$ 回ぐらいになるけど、それを $3^n/2$ 回ぐらいにするためのテクを紹介します。

そもそも 3^n DP って何？

$U = \{1,\ 2,\ \cdots,\ n\}$ とします。競プロ的には $n$ の上限は $15$ ～ $18$ ぐらいのことが多いです。 $U$ の各部分集合 $S\subset U$ に対して $f(S)$ が前計算されているとします。さらに $S\subset U$ に対して $g(S)$ が、「 $S$ の空でない真部分集合 $T\subsetneq S$ に対する $f(T)$ および $g(S\setminus T)$ たち」から計算できるとします。さらにこの計算量は真部分集合の数に対して線形、すなわち $O(2^{|S|})$ でできると仮定します。このとき $g(X)$ が $O(3^{n})$ で計算できます。

どんなとき使えるの？

$U$ の分割（すなわち $k\ (\ge 1)$ 個の非空集合の非交差和 $U=\bigsqcup U_i$ に分ける方法）に対する値が決まっていて、その値を最大化 ¹ するような場合に使えることがあります。

具体例（ネタバレ注意）

例えば この問題 が有名です。以下では、この問題特有の解説は特にしませんが、 AC コードのみ参考に紹介します。

コード

test.py

# X: f に対応。前計算済み
# Y: g に対応。Y[-1] が求めるもの
# merge: 累積

Y = [0] * (1 << n)
for i in range(1, 1 << n):
    j = (i - 1) & i
    s = init(i) # 初期化（S=T の場合の処理もここでする）
    while j:
        s = merge(s, X[i^j], Y[j])
        j = (j - 1) & i
    
    Y[i] = fin(i, s)

上の問題だと AC コード のように書けます。

半分にするテク

概要

$S$ の真部分集合 $T$ をすべて動かすときに、実は $T$ を選んでも $S\setminus T$ を選んでも結果は同じになることがあります ⁴。そのような場合、 $a\in S$ を $1$ つ固定して $a$ を含む真部分集合 $a\in T\subsetneq S$ のみを選ぶ ⁵ という $\mathrm{DP}$ にするとループの回数を半分にすることができます。

コード

先ほどのコードを数行変えるとできます。このコードでは $i$ の最下位 bit a = i & -i を固定して、 $j$ は $ia = i - \{a\} = S - \{a\}$ の非空部分集合をすべて回ります ³ 。

test.py

# X: f に対応。前計算済み
# Y: g に対応。Y[-1] が求めるもの
# merge: 累積

Y = [0] * (1 << n)
for i in range(1, 1 << n):
    ia = i ^ (i & -i) # S - {a}
    j = ia
    s = init(i) # 初期化（S=T の場合の処理もここでする）
    while j:
        s = merge(s, X[i^j], Y[j])
        j = (j - 1) & ia
    
    Y[i] = fin(i, s)

先ほどの問題だと AC コード のようにできます。実行時間は $444\ \mathrm{ms}$ → $266\ \mathrm{ms}$ と短くなっています。 PyPy のオーバーヘッドが $50$ ～ $60 \mathrm{ms}$ ぐらいあるので、ほぼほぼ半分になっていることが分かります。

さらなる定数倍高速化 ⁶

定数倍高速化の基本は、ボトルネックになる部分の処理を軽くすることです。 $3^n$ $\mathrm{DP}$ の場合は、メインの部分以外は $O(2^n)$ あるいは $O(2^n \times n)$ のことが多いので、メインの $O(3^n)$ 回の処理の部分が圧倒的にボトルネックになりがちです ⁷。しかも $O(3^n)$ 部分の処理はとても軽いことが多いので、少しの書き方の違いでも実行時間には大きく影響を与えがちです。例えば、上のコードでは merge 関数を別で書いて呼び出していましたが、ここは直接書いた方が呼び出しコストが減って大きく改善できます。もっと細かい例だと i + 1 みたいな計算を $O(3^n)$ 回やってるなら i1 = i + 1 を $O(2^n)$ 回前計算すると少し速くなるかもしれません。同じランダムアクセスをしている場合も前計算しておくと良いでしょう ⁸。とにかく $O(3^n)$ 部分の処理は必要最小限にというのがポイントですね。

test.py

# X: f に対応。前計算済み
# Y: g に対応。Y[-1] が求めるもの
# merge: 累積

Y = [0] * (1 << n)
for i in range(1, 1 << n):
    # ここは 2^n 回ぐらいしか通らないので多少重くても気にしない
    ia = i ^ (i & -i)
    j = ia
    s = X[i]
    while j:
        # ここは (3^n)/2 回ぐらい通るので極力軽くしたい
        s = max(s, X[i^j] + Y[j]) # 関数呼び出しではなく直接コーディング
        j = (j - 1) & ia
    
    Y[i] = s

関数呼び出しをやめた AC コード では $234\ \mathrm{ms}$ になりました。

経緯

この記事を書こうと思った直接の経緯は、ツイートが分からんと言われてしまったこと。

解説お願いできませんか？（きりさんのツイートで理解できず）

— ながたかな (@ngtkana) July 13, 2021

じゃあ半分にするテクって呼んでおきます

— きり (@kiri8128) January 3, 2021

おしまい

おしまい

1. 合計、 $\max$ 、 $\min$ などを求めることも。 ↩

2. $i$ の下から $k$ bit 目が立っているとき、かつそのときに限り、 $k\in S$ という関係があるよ ↩

3. 集合と（集合を表す）変数を混同している書き方なので分かりにくい
   こんな感じ。変数 $i$ は上の $S$ に、変数 $j$ は $T$ にそれぞれ対応します ²。 $j$ は $i$ の非空真部分集合をすべて回ります ³。 ↩ ↩²

4. $3^n$ $\mathrm{DP}$ の問題だとほとんどがそうだと思います ↩

5. 逆に $a$ を含まないもののみを選ぶとしても同じです ↩

6. 高速化というよりは、定数倍が重くて損しないように注意しましょうという話です。 ↩

7. ただし前計算が $O(2^n \times n^2)$ の場合はそこまで圧倒的でもないかもしれません。 ↩

8. このあたりは言語によっては最適化されるかもしれませんが。 ↩

9. そのままですね
   このテクの名前はよく知らないので、「半分にするテク」と呼ぶことにしました ⁹。 ↩