問題
追加と削除のクエリがあり、それぞれのクエリごとの結果を出力する。
制約上クエリの最大数が多いので、1回の計算量が多いとTLEしてしまう。
……という、C問題界隈ではよくあるいつものやつ。
解説
しかし、アプローチが異なるため初心者は躓きやすい。（１敗）
求められているのは探索アルゴリズムではなく、格納するデータ構造に最適なものを選択できるか、といった感じ。
優先度付きキューを使う。これに要素を追加すると、自動的に優先度順で並べ替えてDequeueやPeeKした時に優先度が最も高いものを出してくれる。
C#にも公式で用意されているのでそれを使うのが平易1。こちらは最小ヒープとなっている。
この優先度付きキューは型引数が2つあるのだが、この問題においては「優先度」と「そのペア」は同じものを表しているため、Enqueue()に同じ変数を指定すればいい。肩透かし
自分で実装するには以下の記事を参照。
感想
その時点でh以下の木が何本あるのか知ることを考えてたけど、どう考えても間に合わないよなあ、と。
薄っすらこんな感じのものがあればいいなあと思ってたがどうにも思い出せず、そもアプローチが違うことに気付いた時にはもう時間がなかった。
優先度付きキュー、二分ヒープ、もう覚えたからな。
コメント