Problem - D - Codeforces (CFR507-D1D) に使いました
以下の条件を満たす $f$ を取り扱います。
- $f$ は整数値を取る
- $f(k) \le N/k$ のように制約される ( $n$ 個のものをどうにかして $k$ 個ずつ個包装したい場合など… )
- $f$ は(広義)単調減少する
$f$ を普通にひとつ計算すると $O(g(n))$ かかるとしましょう。この時、以下の手順で $f(1),f(2),\dots,f(n)$ をまとめて $O(g(n) \sqrt{n} \log{n})$ で計算できます。
まず、 $f(1)$ と $f(n)$ を普通に計算する。
次に、以下の分割統治を定義する。
- [ $l,f(l),r,f(r)$ ] の値を渡しながら再帰的に解く。ここでは $f(l)$ から $f(r)$ までを管理する。
- $l+1 \ge r$ ならば続行する意味が無いので終了。
- $f(l)=f(r)$ ならば $f(l)=f(l+1)= \dots =f(r)$ が判明して終了。
- $m = \lfloor \frac{l+r}{2} \rfloor$ とし、 $f(m)$ を求める。
- 最後に、以下のふたつを呼ぶ。
- [ $l,f(l),m,f(m)$ ]
- [ $m,f(m),r,f(r)$ ]
これで [ $1,f(1),n,f(n)$ ] を呼べば目的達成。
ざっくりした計算量の証明:
$f$ は整数値を取り、その値の種類数は $O(\sqrt{n})$ である。この全部について $f$ がある値以上か未満かの二分探索をすることを考えるが、これでアクセスする部分には上の分割統治でもアクセスされ、アクセスされない部分にはアクセスされないはずである。なので $O(\log n)$ が掛かって全体で $O(g(n))$ を $O(\sqrt{n} \log{n})$ 回呼ぶことになる。
最初に挙げた問題での実装例: Submission #227612376 - Codeforces
ばちゃ中に再発明したけど違う方も同じことやってるコード書いてたし実はけっこう有名そう。もっといい名前とか付いてるのかな
