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