解説


以下、 個の宝石を選ぶ方法があるとして進めます。

まず、明らかに昇順または降順に宝石を並べるのが最適です。 このとき、そのネックレスの不均一さは必ず、最初と最後の宝石の綺麗さの差と等しくなります。

よって、

以上の つを、重さの制約に気を付けながら更新します。 そして であるような 全てについて の最小値が解となります。

計算量は実装によりますが、 程度で可能です。

なお、bit 全探索を用いても同様に解くことができます。