2022.03.02
STAFF BLOG
スタッフブログ
TECHNICAL
テクログ

こんにちは!福神漬けです。
みなさん精力的にAtCoderに取り組まれてると思いますが、今日はそれ関係の話です。
お伝えしておくと自分はC++書いたことがないので聞いたりドキュメント読んだ程度の知識なので、
ゆるーい感じなのをご容赦ください。ブログですし!
multisetとの出会い
ABC241のD問題です。
https://atcoder.jp/contests/abc241/tasks/abc241_d
この問題の肝は保持している数列の大きい順と小さい順の両方を高速で導く必要がある、という点です。
単純な優先度付きキューだと解けない問題ですね。
色々ある解法の中でC++のmultisetを使ったものがとてもシンプルでした。
multisetとは
公式ドキュメント
https://cpprefjp.github.io/reference/set/multiset.html
こちらの方の記事も参考にさせていただきました。
http://vivi.dyndns.org/tech/cpp/multiset.html
かいつまんで説明すると、
・データの追加・削除・検索の処理速度が O(log N)
・内容の重複を許可
・双方向イテレータ(要素を昇順にも降順にも数えられる)
この検索というのは例えば10以下の要素の最初に見つかったもの、
なんていう探し方のことです。
まあつまりこのD問題にぴったりなわけです。
初めて知った時には便利すぎてちょっと叫びました。
おまけ
内容の重複を許可しないものにsetがあります。
https://cpprefjp.github.io/reference/set/set.html
こっちもとても便利(らしい)です。
終わりに
競プロはC++で書かれている解説がほとんどですし、C++勉強するかな〜って元々思っている部分がありましたが、
multisetを知ってモチベがかなり高まってきました。
ちょっとずつやっていきたいと思います。
お疲れ様でした!