総和に制限のある部分和問題の bitset 高速化

1が18個→1+2+4+8+3 にするやつをして、今回の問題だとそこで新たにできた4ともともとある4は同一視できるから4が1個増えたと思っていい
よって下から順番に上の表現に直していくことで、1つ1つの個数を最大2個の状態まで変形することができて、種類数はO(√N)のまま

— てんぷら (@tempura_cpp) July 16, 2019

Θ(N√N/w) が存在した～完～

概要

Aizu Online Judge Arena

HUPC 2019 day2 D が面白く、想定解の工夫と bitset 高速化を併用することで更に高速な解が得られたので紹介します。
→真に高速な解法が提案されたので計算量解析ネタになりました。

問題設定

M: 作りたい値
N: 使用できる要素の個数 (入力および前処理分)
S: 要素の総和
w: ワードサイズ (bitset で w 倍の高速化がされる)

アルゴリズム

基本は部分和問題に用いる一般的なアルゴリズムである dp[i] = (i が作れるか) を更新していく手法を用いますが、同じ値をまとめて処理することを考えます。
ある値について、それが要素の中に k 個存在するとします。

• k >= w
  累積和などを用いた DP で Θ(M) で更新
• k < w bitset を用いて Θ(Mk/w) で更新

このアルゴリズムによって、Θ(N + M√(S/w)) の時間計算量が達成されます

計算量解析

※やや厳密性に欠ける解析です

S を維持したまま要素の構成を変えて、計算量が最大になるようなケースを考えます。
要素に 1 が k 個含まれると仮定します。

• k > w
  1 を 1 つ消して他の要素に加算すると計算量が広義増加します。 k >= w の範囲では DP による更新で計算量が k = w の場合と変わらないためです。
  
• k < w
  2 以上の要素を取ってきて 1 にすれば計算量が広義増加します。k < w の範囲では bitset による更新で個数に比例する計算量が掛かるためです。
  

以上をまとめると、1 の個数が丁度 w 個である場合のみ考えれば良いことが分かります。 同様の議論を 2, 3... について行うことで、ある t について 1 から t が全て w 個ずつ存在する場合のみ考えれば良いことが分かります。 wt² = S を t について解くと t = √(S/w) を得るため、Θ(M) を t 回行うことから Θ(M√(S/w)) を得ます。 前述した問題では想定解 Θ(N√N) に対して √w 倍の高速化になりました。