第6回 ドワンゴからの挑戦状 予選 E - Span Covering の Θ(X^2((log X)^2+log N)+N) 解法

(追記 2022/04/29) : 計算量を  \Theta (X ^ 2 ( ( \log X ) ^ 2 + \log N ) + N ) に改善できたので、追記しました。

問題

atcoder.jp

解法

包除原理の適用を考える。具体的には、

 \displaystyle
A_i:= \text{区間 $[i-1,i)$ が被覆されていないような置き方の集合}

とおき、非負整数  k に対して集合  S_k

 \displaystyle
S_k:=\{(a_0,\ldots,a_k)\mid a_0+\cdots+a_k=X+1,\;\text{$a_i$ は正整数} \}

で定め、

 \displaystyle
\begin{aligned}
\mathrm{ans}
&=\sum_{k=0}^X (-1)^k \sum_{(a_0,\ldots,a_k)\in S_k}
\left\vert \bigcap_{j=0}^k A_{a_0+\cdots+a_j}\right\vert
\\
&=\sum_{k=0}^X (-1)^k \sum_{(a_0,\ldots,a_k)\in S_k}\prod_{i=1}^N\sum_{j=0}^k\max\{0,a_j-L_i\}\\
\end{aligned}

により答えを求める。

 X=15,k=4,(a _ 0,a _ 1,a _ 2,a _ 3,a _ 4)=(3,4,1,5,3)\in S_k の例

 \displaystyle
\begin{aligned}
\sum_{j=0}^k\max\{0,a_j-L_i\}&=\sum_{j\in\{j'\mid a_{j'}\geq L_i\}}(a_j-L_i)\\
&=\left(\sum_{j\in\{j'\mid a_{j'}\geq L_i\}}a_j\right)-L_i\cdot \vert \{j'\mid a_{j'}\geq L_i\}\vert
\end{aligned}

なので、 x に対して  c := \vert \{ j' \mid a _ {j' } \geq x\} \vert および  \displaystyle s := \sum _ { j \in \{ j' \mid a _ {j'} \geq x\}} a_j の値が分かれば

 \displaystyle
\begin{aligned}
\sum_{j=0}^k\max\{0,a_j-x\}&=s-cx
\end{aligned}

として計算することが出来る。そして、これは  a_j\geq x となる  a_j を全て決めてしまえば 以降変化することが無い

以上を踏まえて、次のような DP を考える。

 \displaystyle
\mathrm{dp} [x] [c] [s] := \sum _ { \overset { \scriptstyle a _ 0 + \cdots + a _ {c-1} = s , }{a _ 0, \ldots , a _ {c-1} \geq x} }\prod _ {i \in \{ i' \mid L_{i'} \geq x\} } \sum _ {j=0} ^ {c-1} \max \{0, a _ j - L _ i \}

このテーブルを用れば、

 \displaystyle
\sum_{k=0}^{X}(-1)^k\cdot \mathrm{dp}[1][k+1][X+1]

として答えを求めることが出来る。

 \mathrm{dp} テーブルの計算を考える。初期化は容易であり、

 \displaystyle
\mathrm{dp}[X+2][c][s]=\begin{cases}
1&\text{if $c=s=0$ }\\
0&\text{otherwise}
\end{cases}

とすればよい。更新は、 x の降順に求めていくことにすれば、列  a x を挿入する個数  p で場合分けをし、以下のように計算できる。

 \displaystyle
\mathrm{dp}[x][c][s]=(s-cx)^{\mathrm{cnt}[x]}\sum_{p=0}^{\min\{c,\lfloor s/x\rfloor\}} \binom{c}{p}\cdot \mathrm{dp}[x+1][c-p][s-px]

ここで、 \mathrm{cnt}[x]:= \vert\{i\mid L_{i}=x\}\vert とおいた。二項係数および  \mathrm{cnt} (s-cx) ^ {\mathrm{cnt}[x]} の取得が  O(1) でできる仮定すれば、調和級数の部分和の解析を用いることで、愚直に更新しても全体  \Theta(X ^ 3\log X) でこのテーブルのすべての値を求めることが出来ることが分かる。

このままでも十分高速であるが、少しの工夫でさらに計算量を落とすことが出来る。 c について  c\leq \left\lfloor\dfrac{X+1}{x}\right\rfloor の部分しか見なくてよいこと、 s について  s\geq cx の部分しか見なくてよいことから、べき乗等が  O(1) で求まるという仮定の下で、テーブル更新の計算量は

 \displaystyle
\begin{aligned}
\sum_{x=1}^{X+1}\sum_{c=0}^{\lfloor(X+1)/x\rfloor}\sum_{s=cx}^{X+1} (c+1)&=
\sum_{x=1}^{X+1}\sum_{c=0}^{\lfloor(X+1)/x\rfloor}(X+2-cx)(c+1)\\
&\leq (X+2)\sum_{x=1}^{X+1}\sum_{c=0}^{\lfloor(X+1)/x\rfloor}(c+1)\\
&\leq (X+2)\sum_{x=1}^{X+1}\sum_{c=0}^{\lfloor(X+1)/x\rfloor}\left(\left\lfloor\dfrac{X+1}{x}\right\rfloor+1\right)\\
&\leq (X+2)\sum_{x=1}^{X+1}\left(\dfrac{X+1}{x}+1\right)^2\\
&= (X+2)\sum_{x=1}^{X+1}\left( \dfrac{X^2}{x^2} + O(X) \right) \\
&= O(X^3) \quad\left(\because\sum_{i=1}^\infty \frac{1}{i^2}=\frac{\pi^2}{6}\lt \infty \right)\\
\end{aligned}

となり  \log を落とすことが出来る。また、以下に示すようにこの和は  \Omega(X ^ 3) であるから、即ち  \Theta(X ^ 3) である。

証明

 \displaystyle
\begin{aligned}
\sum_{x=1}^{X+1}\sum_{c=0}^{\lfloor(X+1)/x\rfloor}\sum_{s=cx}^{X+1} (c+1)&\geq 
\sum_{c=0}^{X+1}(X+2-c)(c+1) \quad(x=1\; \text{の部分だけを取り出した})\\
&=\dfrac{1}{6}(X+2)(X+3)(X+4)\\
&\geq \dfrac{1}{6} X ^ 3
\end{aligned}

より、示された。(証明終)

前計算に関して、二項係数に  \Theta(X ^ 2) \mathrm{cnt} \Theta(N)、べき乗に  \Theta(NX) だけかけるとすると、全体  \Theta(NX+X ^ 3) でこの問題を解くことが出来た。

なお、 \mathrm{cnt} が入力として与えられるような場合で  \mathrm{cnt}[x] が非常に大きくなりうるときは、各  x に対して  a ^ {\mathrm{cnt}[x]}\;(0\leq a\leq X+1) \Theta(X ^ 2 \log C) (ただし、 C:= \max_x \mathrm{cnt}[x] とした) だけかけて前計算するなどしてべき乗を高速に求められるようにすれば、全体  \Theta(X ^ 3 + X ^ 2 \log C) となる。なお、都度べき乗を計算しても  \Theta(X ^ 3 + X ^ 2 \log X \log C) である。

実装

提出 (C++, 504ms)

更なる高速化について (2022/04/29 追記)

以下の dp において、各  x=1,\ldots,X+1 に対して  \displaystyle 0 \leq c \leq \left\lfloor \dfrac{X + 1}{x} \right\rfloor の部分だけを見ればよいということであった。

 \displaystyle
\begin{aligned}
\mathrm{dp}[X+2][c][s]&=\begin{cases}
1&\text{if $c=s=0$ }\\
0&\text{otherwise}
\end{cases}, \\

\mathrm{dp}[x][c][s] &= (s-cx)^{\mathrm{cnt}[x]}\sum_{p=0}^{\min\{c,\lfloor s/x\rfloor\}} \binom{c}{p}\cdot \mathrm{dp}[x+1][c-p][s-px].
\end{aligned}

状態数は  \Theta(X ^ 2 \log X) であるが、遷移に  \Theta(c) だけ掛かっていたためテーブル更新の計算量が全体で  \Theta(X ^ 3) となっていた。ここでは、遷移の計算量を削減することで計算量を  \Theta(X ^ 2 (\log X) ^ 2) に落とす方法について述べる。即ち、元の問題は  \Theta (X ^ 2 ( ( \log X ) ^ 2 + \log N ) + N ) 時間で、入力で  \mathrm{cnt} が与えられる場合の問題は、 \mathrm{cnt} の最大値を  C として  \Theta (X ^ 2 ( ( \log X ) ^ 2 + \log C ) ) 時間で解くことが出来る。

dp の更新式を変形をすると、次のようになる。

 \displaystyle
\dfrac{\mathrm{dp}[x][c][s]}{c!} = (s-cx)^{\mathrm{cnt}[x]}\sum_{p=0}^{\min\{c,\lfloor s/x\rfloor\}} \dfrac{1}{p!} \cdot \dfrac{\mathrm{dp}[x+1][c-p][s-px]}{(c-p)!}.

ここで  \displaystyle \mathrm{dp'}[x][c][s]:=\dfrac{\mathrm{dp}[x][c][s]}{c!} と定義すれば、 \mathrm{dp'} は次のように計算できる。

 \displaystyle
\begin{aligned}
\mathrm{dp'}[X+2][c][s]&=\begin{cases}
1&\text{if $c=s=0$ }\\
0&\text{otherwise}
\end{cases}, \\
\mathrm{dp'}[x][c][s] &= (s-cx)^{\mathrm{cnt}[x]}\sum_{p=0}^{\min\{c,\lfloor s/x\rfloor\}} \dfrac{1}{p!} \cdot \mathrm{dp'}[x+1][c-p][s-px].
\end{aligned}

 x を固定し、 V[c][s] := \mathrm{dp'}[x+1][c][s] とおく。各  c, s に対する

 \displaystyle
\sum _ {p=0} ^ {\min\{c,\lfloor s/x\rfloor\}} \dfrac{1}{p!} \cdot V[c-p][s-px]

が高速に求まればよいが、 s = ax + b\; (0\leq b \lt x) と表すと、 求める和は以下のように書ける。

 \displaystyle
S _ b [c][a] := \sum_{p=0}^{\min\{c,a\}} \dfrac{1}{p!} \cdot V[c-p][(a-p)x+b]

従って、多項式  f および  g _ b\; (0\leq b\lt x) を以下のように定義すれば、

 \displaystyle
\begin{aligned}
f(t, u) &:= \sum _ {n = 0} ^ \infty \dfrac{1}{n!} t ^ n u ^ n \\
g _ b (t, u) &:= \sum _ {n = 0} ^ { \lfloor (X + 1) / x \rfloor } \sum _ {m = 0} ^ { \lfloor (X + 1 - b) / x \rfloor } V[n][mx + b] t ^ n u ^ m
\end{aligned}

 S _ b [c][a] = [t ^ c u ^ a] f \ast g _ b として計算される。 b を固定すると  f \ast g _ b高速フーリエ変換などにより  \Theta\left(\dfrac{X ^ 2}{ x ^ 2 } \log X\right) 時間で計算できるので、全ての  b に対して  f \ast g _ b を計算するのは、 \Theta\left(\dfrac{X ^ 2}{ x } \log X\right) 時間で可能である。従って、 \mathrm{dp}' 全体を求めるのにかかる計算量は  \Theta(X ^ 2 ( (\log X) ^ 2 + \log C) ) となる。

上記の解法のボトルネックは畳み込みの計算であり、定数倍は軽くない。 f の形が特殊なことを利用すると、定数倍を多少改善できる。

 \displaystyle
\begin{aligned}
S' _ {b, d} [c] &:= \sum_{p=0}^{c} \dfrac{1}{p!} \cdot V[c-p][(c-p+d)x+b], \\
f' (t) &:= \sum _ {n = 0} ^ \infty \dfrac{1}{n!} t ^ n \\
g' _ {b, d} (t) &:= \sum _ {n = 0} ^ { \lfloor (X + 1 - b) / x \rfloor } V[n][(n+d)x + b] t ^ n
\end{aligned}

として (記号が紛らわしいが、 '微分ではない)、 0 \leq b\lt x,\; 0\leq d\leq \lfloor (X+1-b)/x \rfloor を固定すれば、 S' _ {b, d} [c] = [t ^ c] f' \ast g' _ {b, d} として計算される。従って、 \lfloor (X + 1) / x \rfloor 次程度の多項式の畳み込みを  X+1 回以下だけ行うことで全ての  S' _ {b, d} [c] を計算することが出来る。これは、 \lfloor (X + 1) ^ 2 / x ^ 2 \rfloor 次程度の多項式の畳み込みを  x 回行うよりも定数倍が良い。

なお、 0 \leq d としてよい理由は、 s \lt cx ならば  \mathrm{dp}'[x][c][s] = 0 が成り立つためである。

実装

提出 (C++, 440ms)

 \mathrm{mod}\;10 ^ 9 + 7 での畳み込みということもあって遅いですね。