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回の呼び出しが重い。使う時には注意する必要がある。

AGC 038 C - LCMs

• 問題
• AC

ゼータ変換について勉強する機会になった。

ゼータ変換とメビウス変換

• 下位集合に関するゼータ変換: $F(S) = \sum_{T \subseteq S} f(T)$
• 上位集合に関するゼータ変換: $F(S) = \sum_{T \supseteq S} f(T)$

これを${\mathcal O}(2^N N)$でやるのが高速ゼータ変換。普通の総和以外にも、$\times, \max, \min$とかでもまったく同じ方法が使える。結合法則と交換法則が成り立っていればよいので、可換半群なら大丈夫なはず¹。

• 下位集合に関するメビウス変換: $f(S) = \sum_{T \subseteq S} (-1)^{|S\setminus T|}F(T)$
• 上位集合に関するメビウス変換: $f(S) = \sum_{T \supseteq S} (-1)^{|T \setminus S|}F(T)$

ゼータ変換の逆変換。つまり、上の$F$から$f$を導出する変換。

ゼータ変換と違って引き算を使うので、アーベル群でないといけない。演算が$\min$とかだとそもそも$f$を一意に復元できないので、当然ではある。

（用語法はよくわからないけど、競プロ界ではだいたいみんなnaoya_tさんの記事にある使いわけをしているっぽいのでそれに従っている。文献（これとか）によっては、ここでいう下位集合に対するゼータ変換がMöbius transform、その逆変換がMöbius inversionと呼ばれていたりする。）

$\cup$畳み込みと$\cap$畳み込み

$f$, $g$を
$F(S) := \sum_{T \subseteq S} f(T)$

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

と下位集合に関してゼータ変換して、点毎に掛け算したものを$H$とする:

$\begin{aligned} H(S) & := F(S) \times G(S) \\ & =\sum_{T_1 \subseteq S} f(T_1) \times \sum_{T_2 \subseteq S} g(T_2) \\ & = \sum_{T \subseteq S} \sum_{T_1 \cup T_2 = T}f(T_1) \times g(T_2) \end{aligned}$

$H$をメビウス変換すると

$h(S) := \sum_{T_1 \cup T_2 = S} f(T_1) \times g(T_2)$

という関数が得られて、$\cup$に関する畳み込みができたことになる。

同様に、上位集合に関してゼータ変換して掛け合わせて逆変換すると、$\cap$に関する畳み込みができる。

分配法則を使っているので、この掛け算は足し算と合わせて環になっていないといけない。

約数、倍数に関するゼータ変換とメビウス変換

上と同じ話を約数、倍数について繰り返す。

• 約数に関するゼータ変換: $F(x) = \sum_{d | x} f(d)$
• 倍数に関するゼータ変換: $F(x) = \sum_{x | m} f(m)$

ただし、定義域は$\{0, 1, ..., N\}$とかに決まっているとして、その中だけで計算する。この変換は${\mathcal O}(N \log\log N)$でできる。²

• 約数に関するメビウス変換: メビウスの反転公式参照
• 倍数に関するメビウス変換: 同上

上の$F$から$f$を導出する変換。同じオーダーでできる。歴史的には約数・倍数に関するもののほうが最初に考えられたらしい。

LCM畳み込みとGCD畳み込み

やはり上と同じ話をLCMとGCDについて書き下してみる。

$f$, $g$を
$F(x) := \sum_{d | x} f(d)$

$G(x) := \sum_{d | x} g(d)$

と約数に関してゼータ変換して、掛け合わせたものを$H$とする:

$\begin{aligned} H(x) & := F(x) \times G(x) \\ & =\sum_{d_1|x} f(d_1) \times \sum_{d_2|x} g(d_2) \\ & = \sum_{d | x} \sum_{\operatorname{lcm}(d_1, d_2) = d}f(d_1) \times g(d_2) \end{aligned}$

$H$を逆変換すると

$h(x) := \sum_{\operatorname{lcm}(d_1, d_2) = x} f(d_1) \times g(d_2)$

という関数が得られて、$\operatorname{lcm}$に関する畳み込みができたことになる。

同様に、倍数に関してゼータ変換して掛け合わせて逆変換すると、$\gcd$に関する畳み込みができる。

問題

$\operatorname{lcm}(A_i, A_j) = A_iA_j/\gcd(A_i, A_j)$で、$\gcd(A_i, A_j)$は高々$1000000$なので、同じ$\gcd$毎にまとめて和を計算できれば良さそう。

最終的には、$dp[x]$が$\gcd(A_i, A_j) = x$となるような組み合わせについての$A_i A_j$の総和になってほしいので、とりあえず$dp$を次のように初期化していく。

$dp[A_i] := dp[A_i] + A_i$

$dp$を倍数に関してゼータ変換して$dp[x] := dp[x] \cdot dp[x]$と掛け合わせて逆変換すると、

$dp[x] = \sum_{\gcd(A_i, A_j) = x}A_iA_j$

になっている。このままでは不必要な組み合わせについても加算されているので、

$dp[A_i] := dp[A_i] - A_i^2$

として添え字が同じ組み合わせを除いたあと、$A_iA_j$と$A_jA_i$のダブルカウントを除くためにすべて半分にする: $dp[x] := dp[x]/2$。（ここではなくて一番最後に半分にしてもよい。）

これで$dp[x]$は$\gcd(A_i, A_j) = x$となるような組み合わせについての$A_i A_j (i < j)$の総和になったので、あとは$\gcd$で割りながら総和を取れば答えになる: $\sum_{x = 1}^{1000000} dp[x]/x$

---

1. ググってもそれっぽい言明が見つからなかったけど、かならいさんがそう言ってるのを発見した。 ↩︎

2. noshi91さんの記事に書いてある。 ↩︎