Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

プライオリティキューを使って上位K個を維持する

D - 3N Numbers

を解くためのテクニック。

プライオリティキューの中にまずK個を入れて、次から一つずつ取っていく際に、「一番小さいやつと新しいやつを加えて必要ならば入れ替える」という操作をすることで、プライオリティキューの中に上位K個の要素を保ち続けることが出来ます。この問題では、上位K個の和を求めるということが必要で、これは差分更新で実現しています。

ふつう、N個の要素の中で上位K個というと、まず考えられるのはソートをしてから上位K個をとるというO(NlogN + K)=O(NlogN)のアルゴリズムですが、プライオリティキューを使うとO(NlogK)で求まることになりますから、KがNよりはるかに小さいの場合は、計算量の点で多少有利です。(実際には遅いかも知れませんが)