制約条件:すべての値が等しい
AOJ
中央値(メディアン)に関する問題
OUPC
有志コン
数列
各kに対して
データ構造
BIT
BIT上二分探索
二分探索
最適化テク:解を変形していく(最適性を失わずに)
絶対値やminを扱う問題
座標圧縮
最小コスト
最適化テク:探索候補を絞る
三分探索
スライムやその合体をテーマとした問題
均等に分ける
制約条件:すべての値が等しい
最適化問題
|x-a| + |x-b| + ... + |x-z| を最小にする x が a, b, ..., z のメディアンになる話は有名で、それを拡張すると仕組みがわかった! 問題へのリンク editorial 問題概要 体のスライムがいて、それぞれの強さは となっている。以下の操作を行うことができる …