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