Codeforces Round #598 (Div. 3)E. Yet Another Division Into Teams

問題概要

$n$ 人の人がおり, $i$ 番目の人の能力は $a_i$ である. ここから任意の個数のチームを作成するが, 各チームの人数は $3$ 人以上でなければならない.

チームの多様さをそのチームに属する人間の能力の最大値と最小値の差とする時, 全てのチームの多様さの和を最小にするにはどのように割り振れば良いか？

制約

$3 \le n \le 2\times 10^5$
$1 \le a_i \le 10^9$

解法

まず, 人間の能力でソートしましょう. 能力が小さい方からチームをまとめていく時, 実はチームの大きさは最大でも $5$ 人になることがわかります. この事実を簡単に以下に示します.

$a_1, a_2, a_3, a_4, a_5, a_6$ の $6$ 人でチームを組むことを考えます. なお, $a_i$ は広義単調増加です. このチームを $a_1, a_2, a_3$ と $a_4, a_5, a_6$ の二つのチームに分割する時, 分割する前と後で多様さは $a_6 - a_1$ から $a_6 - a_4 + a_3 - a_1$ に変化します. $a_i$ の単調性から, $- a_4 + a_3 \ge 0$ が成り立ちます. よって, 可能な限りチームを分割するのが最適です.

これに基づけば, $n$ が $3$ の倍数の時は全て $3$ 人チームにして仕舞えば良いです. $3$ の倍数ではない時は面倒なので, dp をしましょう. $dp[i] :=$ ( $i$ 人めまででチームを作った時の多様さの合計の最小値)とすれば, 自分が属しうるチームは定数個しかないので遷移も定数個しかないです.

実装

復元パート、いる？

Submission #147742980 - Codeforces