ARC067 E Grouping

問題概要

1~nn人をA人以上B人以下のグループに分ける.i人組のグループは0個かC個以上D個以下でなければならない.
このような分け方は何通りあるか.
制約:1\leq N \leq 10^3

解法

次のDPを考える.
dp_{ij}=(j人でi人組まで作る場合の数)
とすると,これはいい感じに数学して遷移ができる.これはぱっと見ではO(N^3)でギリギリTLEっぽいが投げるとACする.
実はこの解法のオーダーはO(N^2 \log N)になる.なぜこうなるかを考えてみる.
知りたいのはdp_{NN}なので,j\gt Nについては考える必要がない.よって各iについてN/i回しか遷移しない.
[tex;N]回のループで,合計N/1+N/2+N/3+...+N/N\fallingdotseq NlogN回の遷移が行われる.
トータルの計算量はO(N^2 \log N)になるということである.
この考え方は公式の解説放送でわかりやすく説明されている.
www.youtube.com