ACL Beginner Contest F - Heights and Pairs

• 問題
• AC

$h_i$が互いに異なる場合は$(2N-1)!! = (2N)! / 2^N N!$通りという有名事実がある（後述）。以下、$p_i = (2i-1)!!$とする。

身長$h$の人が$a_h$人いるとする。$i$人の同じ身長を持つ人から$j$ペアを作る場合の数は$\binom{i}{2j}p_j$である。$F(x) = \prod_h \sum_j \binom{a_h}{2j}p_j x^{j}$とすると、$F(x)$の$x^k$の係数$[x^k]F(x)$は$2N$人から身長が同じであるような$k$ペアを作る場合の数に等しい。このとき、残った人、つまり$2(N-k)$人でペアを作る場合の数は$p_{N-k}$通りであり、あとは包除で$\sum_k(-1)^kp_{N-k}([x^k]F(x))$通りと求まる。

$(2N-1)!!$について

$2N$人に$1, 2, ..., 2N$という番号を振ってこの順に並べ、二人ずつ取り除いていくとする。この際、ペアのうちの一人目は必ずその時点で番号が最小の人を選ぶ、としておくと完全な数え上げができる。一人目には$2N-1$通りの人がマッチできて、二人目には$2N-3$通りの人がマッチできて、……となるので二重階乗の記号を使うと$(2N-1)!!$と表せる。

別の考え方もできる。$2N$人を自由な順番で一列に並べて、隣り合う二人をくっつけて$N$ペアを作ることにする。並べ方は$(2N)!$通りあるが、二人組の内の順番は考慮しないので$2^N$で割る必要がある。さらに、$N$ペアの順番も考慮しないので$N!$で割って$(2N)!/(2^N N!)$と求まる。これらは二重階乗の公式も与えている:

$$ (2N-1)!! = \frac{(2N)!}{2^N N!} $$

エイシング プログラミングコンテスト 2020 F - Two Snuke

• 問題

$2(s_1+n_1+u_1+k_1+e_1)+\Delta s + \Delta n + \Delta u + \Delta k + \Delta e \le N$で各変数は非負という条件下で$\Delta s\Delta n\Delta u\Delta k\Delta e$の総和を取る問題。

$d = N - (\Delta s + \Delta n + \Delta u + \Delta k + \Delta e )$とするとき、$\Delta s\Delta n\Delta u\Delta k\Delta e$は$s_1+n_1+u_1+k_1+e_1 \le d/2$の非負整数解の数だけ足される。これは$\binom{\lfloor d/2 \rfloor)+5}{5}$通りだから、求める数は

$$ \sum_{d_1+d_2+d_3+d_4+d_5 + d = N}\binom{\lfloor d/2 \rfloor+5}{5}d_1d_2d_3d_4d_5 $$

に等しい。FPSで考えるなら、$\sum_n nx^n = x/(1-x)^2$を5乗して$\sum_{i} \binom{\lfloor i/2 \rfloor +5}{5}x^{i}$という謎の級数を掛けると、$x^N$の係数が求める数である。後者にBerlekamp-Massey法を適用してみると21次の多項式を分母とする有理式が出てくるので、$x^N$の係数はBostan-Mori法で求まる。

---

そもそも一般に$\lfloor i/2 \rfloor$の多項式を係数にするFPSが有理べき級数になるのかどうかとか、基本的なことがよくわかっていなかった。

与えられたFPS$f(x)$の偶数項、奇数項がそれぞれ有理べき級数$g(x), h(x)$の偶数項、奇数項と一致しているなら、$g$の(0-basedで)偶数項だけ抜き出したもの$(g(x)+g(-x))/2$と$h$の奇数項だけ抜き出したもの$(h(x)-h(-x))/2$を足せば$f(x)$になるので、確かに有理べき級数になる。一般に$\lfloor i/k \rfloor$の多項式を係数とするFPSについても、$1$の$k$乗根を考えれば同じことが言える。

一般化すると、次の性質を満たす$f(x) = \sum_n a_n x^n$は有理べき級数と言える:

$M$個の有理べき級数$f_k(x) = \sum_n b_{k, n}x^n \ (k=0, 1, ..., M-1)$と$N \in \mathbb N$が存在して、$n \ge N$ならば$a_n = b_{n \bmod M, n}$。

HackerEarth - Connected Permutations

• 問題
• AC

求める数を$a_n$とする。長さ$n$の順列を先頭$k$要素が$1, 2, ..., k$の順列であるような最小の$k$で分類して数えると、それぞれ$a_k(n-k)!$通りある。長さ$n$の順列から長さ$n+1$の順列を作ることを考えると、$n+1$は$k$箇所に挿入可能なので$a_{n+1} =\sum_{k=1}^{n}ka_k(n-k)! = \sum_{k=0}^nka_k(n-k)!$。$a_0=0, a_1=1$としてオンラインFFTすると${O}(N \log^2 N)$で解ける。

CodeChef SnackDown 2021 Online Qualifiers - Minimise Difference

• 問題
• AC

問題: 無向グラフが与えられる。出次数の最大値が最小であるようなacyclic orientationを求めよ。

出次数が$D$以下であるacyclic orientationが存在するかどうかの判定問題が解ければよい。判定問題は次のように解ける:

まだ選んでいない頂点の中でトポロジカル順序で先頭にする頂点$v$を自由に選ぶ。この$v$の次数は$D$以下でなければならず、そのような頂点が存在しなければ判定はNOである。存在する場合、$v$から伸びているすべての辺を削除する。以上を頂点の数だけ繰り返す。実装はキューで${O}(N)$でできる。

エクサウィザーズプログラミングコンテスト2021 (ABC 222) G - 222

• 問題
• 提出

与えられた数列を$(a_i)_{i = 0}^\infty \ (a_0=0, a_1 = 2, a_2 = 22, ...)$とする。$M = \begin{bmatrix} 10 & 2 \\ 0 & 1\end{bmatrix}, v= \begin{bmatrix} 0 \\ 1\end{bmatrix}$とするとき、$a_k$は$M^k v$の第一成分に等しい。従って、問題は$v = M^kv$であるような最小の正整数$k$を求めることと言い換えられる。

この問題はbaby-step giant-stepで解ける。$B= \lceil \sqrt K \rceil$とする。$a_0, a_1, a_2, ..., a_{B-1}$について$\mod K$での値をmapのキー、添字をmapの値として保持しておく。（キーが重複する場合、そこでサイクルに入るので、それまでに$0$が見つかっていなければ打ち切ってよい。） $k= iB-j$, $j \in \{0, 1, ..., B-1\}$とする時、$v = M^kv$が成り立つためには$M^j v = M^{iH}v$が成り立つ必要がある。したがって、$i=1, 2, ..., B$について$M^{iB}v$を計算して$a_{iB}$を求め。この値が先に作ったマップに入っていれば対応する添字$j$を取り出すと$k=iB-j$が答えの候補になる。ただし、$M$は正則とは限らないので、$M^j v = M^{iB}v$は必要条件でしかない。つまり、$a_{iB-j} \mod K$が必ず$0$になるわけではない。実際に$M^{iB-j}v$を計算して確認する必要がある。

ハッシュテーブルを使った場合の期待計算量は${O}(\sqrt K)$。

ABC 221 H - Count Multiset

• 問題
• AC

分割数っぽい数え上げなので分割数っぽいDPを考える。

まずは分割数のDPを思い出す。自然数$n$を$k$個の正整数の和に分割する場合の数を$P(n, k)$とする。分割の中に1を含まないものは$n-k$の$k$分割のすべての項を$1$増加させて得られ、分割の中に1を含むものは$n-1$の$k-1$分割に1を付加すれば得られるのだった。漸化式で表すと

$$ P(n, k) = P(n-k, k) + P(n-1, k-1) $$

このDPを、同じ数を$M$個より多くは含まないという制約（以下、単に制約と呼ぶ）に合うように修正することを考える。制約付きの分割の総数を$P'(n, k)$とする。

上の遷移の一つ目の項、つまり分割の中に1を含まないものを$n-k$の$k$分割のすべての項を$1$増加させて得る場合については、制約はそのまま守られるのでこのままでよさそう。一方、二つ目の項、つまり、分割の中に1を含むものを数えたい場合、このままだと1を$M+1$個含むものも数えてしまうことになるので、これを除きたい。

$n$の$k$分割で$1$をちょうど$M+1$個含み、他は制約を満たしているようなものの総数 = $n-(M+1)$の$k-(M+1)$分割で1を含まず、かつ制約を満たしているようなものの総数 = $n-(M+1)- (k-(M+1))$、つまり$n-k$の$k-(M+1)$分割で、制約を満たしているようなものの総数

と言い換えると、最後の量は$P'(n-k, k-(M+1))$に等しいので、漸化式は

$$ P'(n, k) = P'(n-k, k) + P'(n-1, k-1) - P'(n-k, k-(M+1)) $$

となる。

---

スターリング数っぽい数え上げがスターリング数っぽいDPでできる、はけっこう見るけど、分割数っぽい数え上げではうまくいく問題を見た記憶がなくて、遷移を考え始めるまでに時間がかかった……が、例えばJOI 2009 予選 F - ビンゴ がそうだったのを思い出した。

第八回 アルゴリズム実技検定

満点だった。

L - K番目の絶対値

総和の絶対値が$D$以下であるような連続部分列を数える問題が解ければよさそう。累積和$S_i = A_1 + ... + A_i$上で言い換えると各$i$について$|S_i-S_j| \le D$であるような$j < i$を数えればよく、これは$S_0, S_1, ..., S_{i-1}$の中で$[S_i-D, S_i+D]$に含まれるようなものを数えることに等しい。数え上げを${O}(N \log N)$で解くと、全体で${O}(N \log N \log \sum_i |A_i|)$。

順序対を数えることにすれば尺取りでできる。確かに。

M - バランス

SoundHound Inc. Programming Contest 2018 Masters Tournament E - + Graph

O - 色分けトーナメント

• トーナメントは$2 \cdot 2^N-1$頂点の完全二分木とすると、制約$(W_i, L_i)$は$W_i$と$L_i$のLCAまで$W_i$と$L_i$が勝ち上がって$W_i$が勝つこととみなせる。
• ある選手を青に塗ると決めても赤に塗ると決めても有効な塗り方は同数ある。（どの有効な塗り方についても、すべての色を反転したものが有効な塗り方であるため。）

$\operatorname{dp}_v[x] =$頂点$v$を根とする部分木に属する左から$x$番目の選手の色を決め打った時に、部分木$v$に属する選手の塗り方で（部分木$v$に含まれる制約を満たし、かつ）$v$が勝ち上がるようなものの総数、とする。$\operatorname{dp}_v$は$v$の子を$c_1, c_2$として$\operatorname{dp}_{c_1}, \operatorname{dp}_{c_2}$から線形で作れるので、下から処理していけばよい。根に関する$\operatorname{dp}$の総和を2倍したものが答えになる。

各深さの$\operatorname{dp}$の長さの総和はちょうど$2^N$になるので、全体の計算量は${O}(N 2^N + M)$。