ARC 059 E - キャンディーとN人の子供

• 問題
• AC

部分点のケースについて考える。$x_i$が一定の場合、
$g(k, y) := \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とすると答えは$g(N, C)$で、漸化式は

$g(k, y) = g(k-1, y) + x_k g(k-1, y-1) + ... + x_k^y g(k-1, 0)$

$g(0, 0) = 1$

$g(0, y) = 0 \qquad (y \neq 0)$

と書ける。DPすれば計算量は${\mathcal O}(NC^2)$。

元の制約についてもだいたい同じように解ける。

$h(k, y) := \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \sum_{a_1 + ... + a_N = y} \prod_{i=1}^k x_i^{a_i}$

とするとやはり答えは$h(N, C)$で、

$\begin{aligned} h(k, y) & := \sum_{a_1 + ... + a_N = y} \sum_{x_1 = A_1}^{B_1} \sum_{x_2 = A_2}^{B_2} ... \sum_{x_N = A_N}^{B_N} \prod_{i=1}^k x_i^{a_i} \\ & := \sum_{a_1 + ... + a_N = y} \Bigl( \sum_{x_1 = A_1}^{B_1} x_1^{a_1} \Bigr) \Bigl( \sum_{x_2 = A_2}^{B_2}x_2^{a_2} \Bigr) ... \Bigl( \sum_{x_N = A_N}^{B_N}x_N^{a_N} \Bigr) \end{aligned}$

だから、漸化式は

$h(k, y) = h(k-1, y) + \Bigl( \sum_{x_k = A_k}^{B_k} x_k \Bigr) h(k-1, y-1) + ... + \Bigl( \sum_{x_k = A_k}^{B_k} x_k^y \Bigr) h(k-1, 0)$

となって、やはりDPすれば計算量は${\mathcal O}(NC^2)$。

いろはちゃんコンテスト Day2 E - 連呼

• 問題
• AC

AAAが登場しない列を数えて$\binom{N+M-2}{N}$から引く方針が良さそう。

とりあえず、最初の文字と最後の文字の制限がないとして考えてみる。AAAが登場しない列とは、AとAAを$M$個のBの間に挿入してできる列である。Aを$d$個にわけるとして、Aが$x$個、AAが$y$個になったとすると、

$x + 2y = N$

$x+y = d$

より、$y = N-d, x = 2d-N$と整理できる。AとAAの並べ方は$\binom{d}{y }$通りあり、$M$個のBへの挿入の仕方は（両端を含めると）$\binom{M+1}{d}$通りある。したがって、総和は$\sum_d \binom{M+1}{d}\binom{d}{y}$となる。（有効な$d$についてだけ計算する。）

さて、最初の文字がAで最後の文字がBという制限を満たすものを数える。最初がABから始まるパターンとAAから始まるパターンにわけて数えることにする。

最初がABから始まる場合、最後がBなので、AB·B·...·Bの·で示した$M-1$箇所から選んでAかAAを挿入することになる。総和は$\sum_d \binom{M-1}{d} \binom{d}{y}$である。ただし、$x+2y = N-1, x+y =d$ だから$y = N-1-d$である。

最初がAAから始まる場合、AAB·B·...·Bの·で示した$M-1$箇所から選んでAかAAを挿入することになる。総和はやはり$\sum_d \binom{M-1}{d} \binom{d}{y}$である。ただし、$x+2y = N-2, x+y=d$ だから$y=N-2-d$である。

ABC 142 E - Get Everything

• 問題
• AC
• AC (ゼータ変換)

$N$が小さいので、$dp[S] =$ 集合$S$に含まれる宝箱を全部開けられるような鍵の選び方をした時の最小コスト、を目指したくなる。（不可能な場合は$\infty$。）

${\mathcal O}(2^NM)$のDP

鍵$i$で開けられる宝箱の集合を$C_i$とするとき、$dp[\empty] := 0$と初期化して

$dp[S \cup C_i] := \min (dp[S \cup C_i], dp[S]+C_i)$

をすべての鍵と集合について更新して求まるなら話は早い……が、これは集合の包含関係について全部処理しているわけではない。つまり、この方法で最終的に求まるのは$dp[S] =$ 集合$S$に含まれる宝箱を全部開けられて、$S$に含まれない宝箱を一つも開けられないような鍵の選び方をした時の最小コスト、である。しかし、もう少し考えると、求めるのは全体集合に対する最小コストだったので、それでも問題ないことがわかる。¹

コンテスト中はこの辺の理解にぱっと至らなくて、しばらく逡巡してしまった。

${\mathcal O}(3^N + M)$のDP

最初に目指した$dp$を直接求める方法を考えてみる。$dp$をすべて$\infty$に初期化して、

$dp[\emptyset] := 0$

$dp[C_i] := a_i$

とする。（重複する場合は小さい方を選ぶ。つまり、正確には$dp[C_i] := \min (dp[C_i], a_i)$。）$dp$を上位集合に関してゼータ変換すると、$dp[S] =$ 宝箱の集合$S$を一つの鍵で開ける場合の最小コスト、になっている。あとは、

$dp[S] := \min_{T \subseteq S}(dp[T]+dp[S \setminus T])$

を使って順次最小値を確定していけばよい。部分集合の効率的な列挙のやり方は https://topcoder.g.hatena.ne.jp/jackpersel/20100804/1281196966 に書いてある。

---

1. 何個か宝箱の集合クエリを受け取ってそれに対する最小コストを返す問題の場合は、最後に$dp$をゼータ変換すればよい。 ↩︎

ARC 100 E - Or Plus Max

• 問題
• AC

以下、ビット列とそれが表す集合を同一視する。インデックスの集合$S, T \subseteq \{0, 1, ..., 2^N-1\}, |S|, |T| \le 2$が与えられたとき、$S \oplus T$を、インデックス$i \in S \cup T$の中から$A_i$が大きいもの2つを残した集合とする。$\oplus$は結合的で可換なのでゼータ変換が適用できる。つまり、

$F(S) := \oplus_{T \subseteq S} f(T)$

という変換ができる。$f$は$f(S) := \{S\}$でよい。

これで$i \lor j \subseteq K$を満たす$i, j$に対する$A_i + A_j$の最大値が求まるが、実際には$i \lor j \le K$を満たす$i, j$について考えなくてはならない。$i \lor j \le K \Leftrightarrow k \in \{0, 1, ..., K\}$が存在して$i \lor j = k \Leftrightarrow k \in \{0, 1, ..., K\}$が存在して$i \lor j \subseteq k$だから、$i \lor j \le K$を満たす$i, j$に関する最大値は$\max_{k \le K} (F(k)の片方 + F(k)のもう片方)$として累積的に求まる。

---

高速ゼータ変換に関するメモ。高速ゼータ変換は各部分集合$S \subseteq U$の各要素をちょうど一回ずつ重複なく処理するので、集合の合併を取る場合はそのままくっつけて良い。つまり、例えば$g(S) := S$という関数を和集合についてゼータ変換したいとするとき、つまり

$G(S) := \bigcup_{T \subseteq S} g(T)$

を求めるとき、和集合$S_1 \cup S_2$を得る操作で重複を除く必要はない。

---

Common Lispに関するメモ。扱う集合が小さいので珍しくunionを使う気になったら初歩的な失敗をした。非破壊的な合併を書いているつもりでなんとなく(sort (union list1 list2) ...)としたのだけど、unionはリストをコピーするとは限らないのでsortで元のリストが破壊される。(sort (nunion (copy-list list1) (copy-list2 list2)) ...)とするか、あるいはunionしてからcopy-listするのが正しかった。

非破壊的操作はコピーするとは限らないというポイント、わかっているつもりで普段は忘れている。(sort (mapcar ...) ...)みたいなのも(mapcar #'identity list)がlistをそのまま返すような最適化は許されているので、元のリストが保たれるとは限らない。（SBCLでは大丈夫だけど。）本質的には危険なコードをけっこう書いてしまっている気がする。

---

SBCLに関するメモ。SBCLのmergeはいちいちsb-kernel:specifier-typeを呼ぶので1回の呼び出しが重い。使う時には注意する必要がある。