B 問題「コミュニケーション能力(Communication Ability)」解説

満点解法

説明の簡単化のため，

• かがみずくんのコミュニケーションを $c_0$
• 友達になりたい $i(1≦i≦N)$ 番目の人物のコミュニケーション能力を $c_i$ とする．

かがみずくんが人物 $j$ と友達になることを考える．

$(かかる最小のコスト) = \min(|c_j-c_0|,|c_j-c_1|,...,|c_j-c_{j-1}|)$

なので，それを毎回計算すれば答えが求まる．

しかし，これを毎回時間計算量 $O(N)$ で計算していては時間切れになってしまう．

そこで，数直線上に $c_0,c_1,...,c_{j-1}$ をプロットしてみれば自明ではあるが，$|c_x-c_j|$ が最小となる$c_x$は，

• $c_j≦c_x$ を満たす最小の $c_x$
• もしくは $c_j>c_x$ を満たす最大の $c_x$

であることを利用する（ただし条件を満たす $c_x$ が存在しない場合考慮しない）．

これらの値を求めるためには，$c_0,c_1,...,c_{j-1}$を常にソートした列を保持しておき，それに対し二分探索を行えるようなデータ構造が必要となる．

そのためには，要素の追加・二分探索の両方が時間計算量 $O(\log N)$ で行える平衡二分木を用いると良い．

C++であれば，STL(スタンダード・テンプレート・ライブラリ)にsetという平衡二分木クラスが備わっており，lower_bound/upper_boundメソッドを用いて二分探索を行うことができる．

平衡二分木を用いた場合，今回の問題における時間計算量は $O(N \log N)$ となり時間制限に間に合う．