yukicoder No.1970 ひよこ鑑定士 (yukicoder contest 346 G)

解説が存在しなかったので、取り急ぎ雑ですが作りました。

問題概要

ヒヨコがオスメスそれぞれ $N$ 匹ずつ並んでいる。オス同士、メス同士が区別できないとき、並べ方は $\binom{2N}{N}$ 通りあるが、このうち、オスとメスの匹数の差が $K$ 匹となる連続したヒヨコの区間を選ぶことができる並べ方は何通りか。

置き換え

$P=(P_{1},P_{2},...,P_{2N})$ は、各要素が $+1$ $-1$ のどちらかであり、同数含んでいる。長さ $2N$ の整数列 $S=(S_{1},S_{2},...,S_{2N})$ が $S_{i}=\sum_{j=1}^{i}P_{i}$ を満たすとき、 $S$ の最大値と最小値の差が $K$ 以上になる $P$ の場合の数は何か。

解き方概要

余事象を求めて全体から引けば良いです。つまり、最大値と最小値の差が $K$ 未満になる数を求めて、 $\binom{2N}{N}$ から引けば良いです。

ここで、最小値を $D$ と固定します。すると最大値は $D+K$ 未満でなければいけません。

「最小値が $D$ で最大値が $D+K$ 未満の $S$ の場合の数」は、「最小値が $D$ 以上で最大値が $D+K$ 未満の $S$ の場合の数」から「最小値が $D+1$ 以上で最大値が $D+K$ 未満の $S$ の場合の数」を引いたものに等しいです。

この、「最小値が $D$ 以上で最大値が $D+K$ 未満の $S$ の場合の数」を鏡像法を用いて求めます。

イメージとしては下の図のようです。

この数直線上を初期値として左右に $2N$ 回動いて、原点 $O$ に戻る場合の数を求めれば良いです。

形式的には表すと以下のようである。

無限の数列 $dp$ があり、初期値は $i\equiv 0\;(mod\;(2K+2))$ を満たす $i$ に対して $dp_{i}=1$ 、$i\equiv 2(D+K)\;(mod\;(2K+2))$ を満たす $i$ に対して $dp_{i}=-1$ 、それ以外は $dp_{i}=0$ とします。

全ての $i$ に対して同時に $dp_{i}\leftarrow dp_{i-1}+dp_{i+1}$ と更新する操作を $2N$ 回行った後の $dp_{0}$ の値が求める値です。

これはもちろん独立に求めることができるので、「最小値が $D$ 以上で最大値が $D+K$ 未満の $S$ の場合の数」は以下の式で求まります。

$\sum_{(K+1)|i}(\binom{2N}{N-i}-\binom{2N}{N-i-D-K})$

今、 $D$ を固定化していましたが、この上記の式を $-K+1$ 以上 $0$ 以下の全ての $D$ について求めれば良いです。この値は実は以下の式となります。

$\sum_{(K+1)|i}(K+1)\binom{2N}{N-i}-2^{2N}$

先ほど示したイメージだと以下のようになります。