COMPANY SERVICE STAFF BLOG NEWS CONTACT

STAFF BLOG

スタッフブログ

TECHNICAL

テクログ

2022.03.02

へーってなったC++の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
こちらの方の記事も参考にさせていただきました。
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を知ってモチベがかなり高まってきました。
ちょっとずつやっていきたいと思います。

お疲れ様でした!

この記事を書いた人

福神漬け

入社年2017年

出身地チーバくんの目のあたり

業務内容開発やりつつちょっと管理っぽい仕事

特技・趣味ゲームとゲームをしながらゲームをできること

テクログに関する記事一覧

TOP