关于 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=\{x_{1\cdots w}\}，B=\{y_{1\cdots k}\}，套用引理即可。

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

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

[^1]: 这里其实有个特殊情况，就是 x_1=w，然后 x_1 前的前缀和最小会达到 -w+1，这样一来 x_1 处的前缀和会达到 -2w+1，在 w=2 时会炸。但 x_1 前的前缀和达到 -w+1 时 x 会全是 w，所以选后面的 x 就行。