[题解] CF924F Minimal Subset Difference

关于本题的一个注记。

钦定背包上界为 $72$，这样搜得的状态数为 $12880$。对其进行 dfa 最小化，状态数优化到 $715$（注意到设上界较大时最小化 dfa 后大小仍为该值）。预处理 $f_{k,i,s,r}$ 表示限制差 $\le k$，$i$ 位待定，当前 dfa 上状态为 $s$，当前位至多取 $r$ 的答案，即可 $\mathrm{O}(\log r)$ 回答单组。远古最优解代码。

这题在徐哲安的 2021 年集训队论文《浅谈有限状态自动机及其应用》中作为例题出现，其证明了背包上界只需开到 $80$ 即可，但没证 $72$。以下是我口胡的证明。

结论：对于一个只包含 $\le w$ 的正整数的序列，给每个数安排正负号，使得和的绝对值最小。那么最大前缀和绝对值 $\le w(w-1)$。

引理（CF618F）：对于大小 $\ge n$ 的可重集合 $A$ 和任意大小（设为 $m$）的可重集合 $B$，它们的元素都是 $\le n$ 的正整数。如果 $n+\sum_{b\in B}b>\sum_{a\in A}a$，那么可选两者各自的一个非空子集，使得和相同。证略。

证明：首先最优答案一定 $\le w$，并且当且仅当序列为奇数个 $w$ 时最优答案为 $w$，这是易证的。接下来只考虑最优答案 $\le w-1$ 的情况。

考虑某组最优解，找到其最靠前的前缀和绝对值 $>w(w-1)$ 的位置 $t$，不妨设该前缀和是正的。取出该前缀中最靠后的 $w$ 个取正号的数 $x_{1\cdots w}$，以及剩余后缀中所有共 $k$ 个取负号的数 $y_{1\cdots k}$。其中由鸽巢原理，$x_1,\cdots,x_w$ 一定是可以取出来的，而由于 $\sum_{i=1}^ky_i\ge w(w-2)+2$，故 $k\ge w-1$。

接下来的目标是选择某些 $x$ 和某些 $y$，改变它们的符号，使全体和不变，且 $t$ 及之前不反而出现前缀和 $<-w(w-1)$ 的情况，且 $t$ 处的前缀和降低。这样就可以不断归纳了。

如果 $\sum_{i=1}^wx_i\le w(w-1)$，则令 $A=\set{x_{1\cdots w}}$，$B=\set{y_{1\cdots k}}$，套用引理即可。

否则随意套用引理可能会导致 $x_1$ 处前缀和 $<-w(w-1)$。这时，$x$ 中必然有 $w$。如果 $y$ 中也有 $w$，那么选这两个互换符号即可¹。

否则，选择 $y$ 中最短的前缀 $y_{1\cdots k^\prime}$，使得和 $\ge w(w-2)+2$。由于 $y$ 中无 $w$，故 $k^\prime\ge n$。这时由于 $w(w-2)<\sum_{i=2}^wx_i\le w(w-1)$，$\sum_{i=1}^{k^\prime}y_i\le w(w-1)$，故可令 $A=\set{y_{1\cdots k^\prime}}$，$B=\set{x_{2\cdots w}}$，套用引理即可。