第6回ドワンゴからの挑戦状予選 E - Span Covering

本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。

解法

包除原理の適用

土地を $X$ 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 $z$ について、 $z$ に含まれるマスだけに全てのシートを置く（ $z$ の全てのマスを埋める必要はない）ような置き方の数を $C(z)$ とします。 $z$ として考えられる $2^{X}$ 個全ての集合からなる集合を $Z$ とすると、包除原理より答えは

$\displaystyle \sum_{z\in Z} (-1)^{X-|z|}C(z)$

となります。

この $z$ を全て数えるのはもちろん無理なので上手くまとめます。 $z$ に含まれるマスの、連続しているマスの長さの組に注目します。例えば $z$ に含まれるマスを o、含まれないマスを . として $X$ 個の並びが ..ooo..o..o. のようになっている場合、連続しているマスの長さは順に $3, 1, 1$ です。これを $A(z) = \lbrace 3, 1, 1\rbrace$ のように配列として書くことにします。

$z$ にシートを置く置き方の総数はこの $A(z)$ のみに依存します。そしてある配列 $A$ に対応するような $z$ の個数は、連続しているマス領域の数 $n$ と $z$ に含まれるマスの総数 $s$ を用いて $_{X-s+1}C_{n}$ と計算できます。

f:id:betrue12:20200115060113p:plain

つまりこの $n, s$ が等しいような $A$ についても扱いをまとめて良いことになります。そのためやるべきことは、

$s$ 個のマスを連続する $n$ 個のマス領域に分割する方法 $A$ 全てについての、その $A$ に全てのシートを置く置き方の個数の総和

を全ての $s, n$ について求めることになりました。これに係数 $_{X-s+1}C_{n}(-1)^{X-s}$ を掛けて合計したものが答えになります。

DPを組む

ではこれをどのように求めましょうか。連続するマス領域を1つずつ増やしていくDPを検討します。

まず、各シートについて「そのシートを置ける場所の数」は独立です。これを全てのシートについて掛け合わせたものが置き方の総数になります。

長さ $x$ の連続マス領域を1つ追加した場合、長さが $x$ 以下のシートそれぞれについて置ける場所の数が増えます。具体的にシートの長さが $L_{i}$ である場合、置ける場所は $\max(0, x-L_{i}+1)$ 個増えます。本解法でやりたいことは、このときのシートの置き方の総数の変化を変化前後で変動する倍率を掛けるように扱うことです。

f:id:betrue12:20200115061647p:plain

そしてこの比率を計算するのに $A$ の要素を全て覚えておく必要はありません。シートの長さが $L_{i}$ であり、 $A$ のうち長さ $L_{i}$ 以上の連続マス領域だけについてその領域数が $n$ 、マス総数が $s$ であったとします。このときこのシートを置ける場所の数は $s-nL_{i}+n$ 個あります。そして $L_{i}$ より短い連続マス領域は置ける場所数に影響しません。

このことから、連続マス領域を長いものから順に足していくと扱いやすくなります。なぜならば連続マス領域を足した時に影響を受けるシートが徐々に減っていき、そして影響を受けるシートについては $n, s$ の値だけを用いて連続マス領域を足す前後のシートの置き方を計算できるという非常に良い性質が生まれるからです。これを用いて以下のようなDPの遷移を計算できます。

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ ： $s$ 個のマスを長さ $x+1$ 以上の連続マス領域 $n$ 個に分割する方法 $A$ 全てについての、その $A$ に全てのシートを置く置き方の個数の総和

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ から長さ $x$ の連続マス領域を $k$ 個置いて遷移することを考えます。遷移先は $n_{2}=n+k, s_{2}=s+xk$ として $dp\lbrack x-1 \rbrack\lbrack n_{2} \rbrack\lbrack s_{2} \rbrack$ です。このときの係数を計算します。

都合上 $n \gt 0$ 、つまり遷移前に1つ以上の連続マス領域が既に存在しているとします。長さ $x$ の連続マス領域を足す際には、 $L_{i} \le x$ であるようなシート $i$ について置ける場所の数が変動します。これまで追加されている連続マス領域は全て長さが $x$ より大きいので、これらのシートを置ける場所数の積は

遷移前： $\prod_{L_{i} \le x}(s-nL_{i}+n)$

として計算され、長さ $x$ のシートを $k$ 個置いた後は先ほどの $n_{2}, s_{2}$ を用いて

遷移後： $\prod_{L_{i} \le x}(s_{2}-n_{2}L_{i}+n_{2})$

と計算されます。これらの値は $L_{i}$ を予めソートして、各 $n, s$ ごとに累積「積」を前計算しておけば $O(1)$ で得られます。

$dp\lbrack x \rbrack\lbrack n \rbrack\lbrack s \rbrack$ にこの遷移前後の比を掛け、さらに $k$ 個の領域を既存の $n$ 個の領域の並びにどう混ぜるかの係数 $_{n+k}C_{k}$ を掛けて、 $dp\lbrack x-1 \rbrack\lbrack n_{2} \rbrack\lbrack s_{2} \rbrack$ に遷移させれば良いです。

$n=0$ からの遷移を含めると少し面倒なのですが、以下リンク先のACコードでは以下のように対処しています。

遷移前に $n=0$ であり、最初に追加する連続マス領域の長さが $x \lt \max L_{i}$ である場合には遷移しない。（一番大きいシートの置き場所がなくなってしまうため）
遷移前に $n=0$ である場合、遷移前の置ける場所数は $1$ とする。
遷移後も $n_{2}=0$ である場合、遷移後の置ける場所数も $1$ とする。
最後に答えを計算する際に、 $n=0$ であるようなものは答えに算入しない。（これは本来 $0$ であるべきだが、上記の計算手順を踏むと $dp\lbrack 0 \rbrack\lbrack 0 \rbrack\lbrack 0 \rbrack = 1$ となってしまうため）

計算量について

最後にこの解法の計算量を評価しておきます。前計算は $O(NX^{2})$ です。

DPパートは $x, n, s, k$ についての4重ループです。ここで $n$ は遷移前に長さ $x+1$ 以上の連続マス領域を置いた個数、 $k$ は長さ $x$ の連続マス領域を新しく置く個数なので、最大値はおよそ $\frac{X}{x}$ になると考えられます。 $s$ は評価が難しいのでおよそ $X$ 通りだとしておきます。