コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1159 (記事作成時点)

供養

解法

色ごとに $a_{i}$ を集めた集合をそれぞれ $R, G, B$ とする
$R, G, B$ がそれぞれ偶数要素からなる集合であった場合、同じ色同士で適当に組ませればよいので $0$ が答え
- 以降、$R, G$ が奇数、$B$ が偶数とする
  - $R, G, B$ は適当に読み替えてよい
  - 1色だけや3色すべてが奇数になることはない
$R$ のうち1頭と、$G$ のうち1頭は必ず異なる色と組ませることになるが、$R, G$ のそれ以外はそれぞれ同じ色で組ませればよい
- ある色のうち $k \ge 3$ 頭が異なる色と組んでいるとき、組んでいる相手のうち少なくとも2頭は同じ色なので、それぞれを同じ色で組ませれば必ず不満の総和が小さくなる
- そのときは $k - 2$ 頭が異なる色と組んでいる状態
上記より異なる色の組み合わせは $(R, G)$ もしくは $(R, B) + (G, B)$
ある色 $A$ の各要素について、ある色 $B$ の要素から最も不満が小さくなるように選んだ場合の不満を $D_{A, B}$ とする
- $A, B$ それぞれについて昇順にソートしておけば尺取りで高速に求められる
$(R, G)$ は $D_{R, G}$ の最小値
$(R, B) + (G, B)$ は以下のように求められる
- $D_{B, R}$ のうち $i$ 番目に小さい値を出す要素を $r_{i}$、$D_{B, G}$ のうち $j$ 番目に小さい値を出す要素を $g_{j}$ とすると、以下のように求められる \begin{align} (R, B) + (G, B) = \begin{cases} D_{B, R}[r_{1}] + D_{B, G}[g_{1}] & \mathrm{if} \; r_{1} \neq g_{1} \\ \mathrm{min}(D_{B, R}[r_{1}] + D_{B, G}[g_{2}], D_{B, R}[r_{2}] + D_{B, G}[g_{1}]) & \mathrm{else} \end{cases} \end{align}
$(R, G)$ と $(R, B) + (G, B)$ のうち小さいほうが答え