実用的に高速
コード
SubsetSumNewton.cpp \( O(n + t\log t) \) と SubsetSumRecursive.cpp \(O(n + t \log^2 t)\)
SubsetSumNewton.cpp · GitHub
概要と意訳
Ce JinさんとHongxun WuさんのA Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sumを読んだhttps://arxiv.org/abs/1807.11597。著者を調べるとcodeforcesでLGMだった。
参考文献も読んだhttps://arxiv.org/abs/1004.3412。
Subset Sum問題
正整数列\( s_1 \dots s_n \)と正整数\( t \)が与えられる。\( k=1 \dots t \)それぞれについて、\( s \)の部分列で、和が\( k\)になるものの個数を1000000007で割った余りを求めよ。
ただし、同じ部分列でもインデックスが異なれば別のものとして数える。
- 例
入力 s = { 1, 1, 2, 3 }, t = 7
出力 2 2 3 3 2 2 1
k=3になるものは {1, 2}, {1, 2}, {3}の3通り
Near-Linear Pseudopolynomial Time Randomized Algorithm
アルゴリズムは時間計算量\( \tilde{O}(n+t) \)。Õはsoft-Oと読み、\( \tilde{O}(n)\)は\(O(n \log^k n)\)の略記らしい。論文中にあるものは\(O(n + t \log^2 t)\)と\(O(n + t\log t)\)。
クラシックな\(O(nt)\)の動的計画法と比べると速い。
時間計算量は入力の長さだけでなく入力の値にも依存する。
「和がちょうどtになる部分列が存在する」ことを判定するにはmodをランダムな素数で試す必要がある。論文で述べられているのは上記の問題を解く決定的アルゴリズムなので、競技プログラマーには場合の数問題のほうがインパクトが大きい気がする。
計測
青線newtonは指数関数を参考文献のニュートン法で実装した\(O(n + t\log t)\)アルゴリズム。
赤線recursiveは指数関数を論文で紹介された方法で実装した\(O(n + t\log^2 t)\)アルゴリズム。
黄線dpは動的計画法\(O(nt)\)アルゴリズム。
ニュートン法はt+1を２の冪に切り上げるため階段状になった。
recursiveは分割統治なのでtが２の冪に近いと比較的ロスが少ない。２の冪であるときにニュートン法に追い付いているが、これはニュートン法の計算量は定数倍がやや大きいためだと思われる。
