$K$ 個を選ぶ最適化における乱択アルゴリズム

概要
簡単な例
問題例
適用できない場合
1. https://codeforces.com/contest/1891/problem/E
関連記事

概要

この記事の手法の一部を掘り下げたものです．少し適用例が集まったので記事化．

~~残念ながら，計算量オーダーの証明はしていないです，HELP．~~ → 解決しました．

簡単な例

手法の説明のため，次の自明な問題を考えます．

$N, K$ および整数列 $A = (A_{0}, \dots, A_{N - 1})$ が与えられる．相異なる $K$ 個の添字 $i_{1}, i_{2}, \dots, i_{K}$ を選んだとき， $A_{i_{1}} + A_{i_{2}} + \dots + A_{i_{K}}$ としてありうる最大値を求めよ．

もちろんこれは，ソートして大きいものから足すだけで解けるのですが，その解法は一旦忘れます．

計算量は劣るものの，自然な解法のひとつとして， dp による解法を考えます．次のように dp[i][j] を定義して適切に計算すれば，この問題は $Θ (N^{2})$ 時間で解くことができます．

dp[i][j]： $A_{0}, \dots, A_{i - 1}$ のうちから $j$ 個選んだときの総和の最大値．

この解法を乱択アルゴリズムを利用して高速化します．

簡単のため，最適解のひとつを固定し，最適解が唯一であるかのように記述します．

長さ $N$ かつ総和 $K$ であるような $01$ 列全体の集合を $S_{N, K}$ と書くことにします．最適解は， $S_{N, K}$ の要素のひとつと見なせます．

入力をシャッフルしましょう．すると， $S_{N, K}$ のすべての要素が等確率で最適解を与えるようになります．

許容できる誤答確率 $ε > 0$ を適当に定めます．幅 $w$ を次を満たすようにとります：

$S_{N, K}$ 内の $01$ 列 $x = (x_{0}, \dots, x_{N - 1})$ を乱択するとき，確率 $1 - ε$ 以上で次が成り立つ：

任意の $0 ≦ n ≦ N$ に対して， $| ⌊ K n / N ⌋ - \sum_{i < n} x_{i} | ≦ w$ ．

このように $w$ をとり，dp[i][j] のうち $| ⌊ K i / N ⌋ - j | ≦ w$ を満たす部分のみを計算すれば，確率 $1 - ε$ 以上で最適解を計算できることが分かります．各 $i$ に対して $2 w + 1$ 個程度の $j$ のみを扱うため，計算量は $Θ (N w)$ となります．

以下は， $N = 2 K$ の場合の数値計算です． $ε = 10^{- 4}, 10^{- 5}, \dots$ に対して，誤答確率 $ε$ 以下となる最小の $w$ を求めています．

$(N, K, w)$ を決めると失敗確率 $ε$ は dp で計算できるのでそれをやっています．（ソースコード）

$N$	$K$	$ε = 10^{- 4}$	$ε = 10^{- 5}$	$ε = 10^{- 6}$	$ε = 10^{- 7}$	$ε = 10^{- 8}$	$ε = 10^{- 9}$
100	50	11	12	13	14	15	16
1000	500	35	39	42	46	49	51
10000	5000	111	123	134	145	154	163
100000	50000	352	390	426	458	489	517
1000000	500000	1112	1235	1346	1449	1545	1636

上の数表などから，次が成り立つと考えました．

【定理】 $ε$ を定数とするとき， $w = Θ (\sqrt{N})$ にとることができる．

ランダムウォークで期待値からの乖離の最大が $\sqrt{N}$ のオーダーになるという種類の事実はいくつか知られていると思いますが，本記事の問題では単なる $01$ 列全体ではなく総和が $K$ という制約があるのが厄介で，これに近い結果が知られているかどうかは確認できませんでした．

→ 既存研究があることを教えていただきました！ありがとうございます！（https://twitter.com/knewknowl/status/1691489279762161664）

ランダムウォークというよりは，sampling without replacement というような検索ワードが適しているようです．少し調べたところ，

https://arxiv.org/pdf/1309.4029.pdf

例えばこの論文の定理 2.4 で $n = N / 2$ とすると， $w$ を定めたときの誤答確率を定数 $c$ によって $\exp (- c w^{2} / N)$ 以下と評価できそうです．本記事の記号でいえば $ε$ を固定すると $w$ は $Θ (\sqrt{N})$ ととれるということも分かりますし， $ε$ に対する依存も含めると $w$ は $Θ (\sqrt{N \log (ε^{- 1})})$ にとれるということになると思います．

結局，上の表のような $(N, K, ε, w)$ に対して，誤答確率 $ε$ 以下であるような計算量 $Θ (N w)$ の解法があるというのが結論となります． $ε$ を固定すると $w = Θ (\sqrt{N})$ にとることができて，時間計算量は $Θ (N^{1.5})$ ということができます．

問題例

想定解とは異なる別解として本記事の手法を使うことができる問題たちです．想定解には触れません．

https://codeforces.com/contest/436/problem/E

$0, 1, 2$ からなる長さ $N$ の列で，総和 $W$ のものを最適化する問題です．

これは $01$ 列ではなく $012$ 列ですがが，やはり適当に $w$ を $\sqrt{N}$ の定数倍程度にとり，シャッフルしたあと， $n$ 個選んだ時点で総和が $[W n / N - w, W n / N + w]$ にあるもののみを計算対象とすることで， $Θ (N^{1.5})$ 時間で解けます．

なお本問題では解の復元を要求しており，しかも $Θ (N^{1.5})$ メモリ使うと私の実装では MLE しました． $\sqrt{N}$ ステップごとに dp テーブルを保存しておき，復元時に区間ごとに dp テーブルを再計算することで，時間計算量 $Θ (N^{1.5})$ ，空間計算量 $Θ (N)$ が達成できて，この方法で AC できることが確認できました．

解答例：https://codeforces.com/contest/436/submission/218884165

本問は別の言い方とすると，長さ $3$ の列 $N$ 個の min-plus convolution の結果の第 $K$ 項ということに．長さ $3$ であることは特に使っておらず，短い列 $N$ 個という状況で似たことが出来ます．

https://codeforces.com/contest/739/problem/E

div1 の 3000 点の問題なので，まあまあ高難易度に置かれている問題です． $\sum a_{i}$ と $\sum b_{i}$ が決まっていて， $2$ つの $01$ 列 $a_{i}, b_{i}$ を最適に選ぶ問題です．

列が 2 つあっても同じことができます．ランダムシャッフルの結果，列 $a$ や列 $b$ の累積和の誤差が $w$ を超える確率がそれぞれ $ε$ 以下なのですから，「どちらかの誤差が $w$ を超える」確率は $2 ε$ 以下です．

あとは簡単な dp によって，誤答確率 $2 ε$ 以下，計算量 $Θ (N w^{2})$ で解くことができます．評価関数の構造とかは何も考察する必要がありません．

計算量は，愚直 dp での $Θ (N^{3})$ から $Θ (N w^{2})$ に． $w = Θ (\sqrt{N})$ ととれば $Θ (N^{2})$ 時間です．

なお，シャッフルをすることにより任意の入力に対して誤答確率を小さくできるというのが本記事の手法の良さでもありますが，そもそもテストケースが何らかのランダムによって作られたりしていれば入力をシャッフルしなくても AC したりします．

解答例：https://codeforces.com/contest/739/submission/218639365

https://codeforces.com/contest/1799/problem/F

これも上の問題と同様， $2$ つの $01$ 列を最適に選ぶ問題です．解法も全く同じです．

解答例：https://codeforces.com/contest/1799/submission/218644087

https://atcoder.jp/contests/past202005-open/tasks/past202005_o

総和が $M$ であるような $01$ 列の $3$ つ組を最適化する問題です．愚直に dp しようとすると $Θ (N^{4})$ になりそうですが，やはり $Θ (N w^{3})$ になります．

私がこの手法をはじめて目にしたのがこの問題の QCFium さんによる解説です．この記事では， $Θ (N^{4})$ 解法の定数倍高速化手法として紹介されていますが， $w = Θ (\sqrt{N})$ ととれることから，これは $Θ (N^{4})$ から $Θ (N^{2.5})$ へのオーダー改善ということになります．