概要

各調和度について、実現に必要な移行コストを求めればこの問題も解けます。

調和度が \(y\) と固定されていたときの解法を説明します。まず \(A_i \leq y\) であるような人は無視して考えます。また各楽器について、初期状態で楽器を担当する人のうち最も移行コストの高い人はその楽器を担当することに固定します。まだ担当が決まっていない楽器に余った人を移行コストの少ない順に割り当てます。

これを \(y\) を上げていきながら高速に求めるには、結局整数集合からある要素を削除する操作と、集合の要素のうち \(k\) 番目に小さい要素までの総和を答えるクエリに静的に答えることができればよいです。これは移行コストでソートされた列の Segment Tree を用いればよいです。(もう少し追加制約があり、 Segment Tree は実際には使わないでも解けます)

詳細や解答例

解説スライド

小課題 1 コード

小課題 3 (満点) コード