Pythonで順序付き集合の処理をしようとして苦労することが多い.そこで,順序付集合はC++で解けるようにしておきたい.
使うのは<set>
.この中に,キーの重複を許さないset
と,キーの重複を許すmultiset
がある.ソートを保ったまま,要素の挿入(insert
)を対数時間で処理できる.
set - cpprefjp C++日本語リファレンス
イテレータ,lower_bound,upper_boundについては以下がわかりやすい.
AI - 4.04.イテレータ
- lower_bound:「指定した値以上の最小の要素」を指すイテレータを返す.見つからなかった場合は、範囲の最後を返す.
- upper_bound:「指定した値より大きな最小の要素」を指すイテレータを返す.見つからなかった場合は、範囲の最後を返す.
std::set
重複がない集合を扱うことができる.set - cpprefjp C++日本語リファレンス
ABC217D - Cutting Woods
D - Cutting Woods(C++解法:(C++) ABC217D - Cutting Woods - 競プロはじめました)
(Python解法:ABC217D - Cutting Woods - 競プロはじめました)
std::set
を使った解説:Editorial - AtCoder Beginner Contest 217std::set
を使った回答:Submission #26210749 - AtCoder Beginner Contest 217
std::multiset
重複がある集合を扱いたい場合はこちらを使う.multiset - cpprefjp C++日本語リファレンス
ABC241D - Sequence Query
D - Sequence Query(C++解法:(C++)ABC241D - Sequence Query - 競プロはじめました)
ABC245E - Wrapping Chocolate
E - Wrapping Chocolate(C++解法:ABC245E - Wrapping Chocolate - 競プロはじめました)