ペペロ交換

高さ $t$ 以下の塀だけをつなぐと、費用 $t$ 以下の組は同じ連結成分内に限られる。大きさ $s$ の成分では高々 $\lfloor s/2\rfloor$ 組を作れる。塀を高さの昇順に処理し、各成分で可能な限り組を作り、人数が奇数なら一人だけ残す。高さ $h$ の塀で奇数人数の二成分を併合するときだけ、残った二人で費用 $h$ の組を作る。それ以外の併合では新しい組を作らない。残った二人の間の最大の塀はちょうど $h$ である。この構成はすべてのしきい値 $t$ で、費用 $t$ 以下の組数の上限を同時に達成する。よって組の費用を昇順にした各値は、他の完全マッチングの対応する値以下であり、総和も最小である。整列と DSU で時間 $O(N\log N)$、領域 $O(N)$。サブタスク $1$ は残った最初の人と相手をすべて試す部分集合 DP で、時間の上界は $O((2N)^2 2^{2N})$。

Solution written by GPT6.1