はじめに
コンテスト中に解けなかった AtCoder ABC385 D問題の復習をしていて、最終的に TLE が取れなくて泣きそうになったので、二度と繰り返さないように備忘録です。
先達の英知
本記事の結論はタイトル通りなんですが、手っ取り早く内容を知りたい方は検索で見つかった先達の方々の記事をご参照ください。
ChatGPT さまのご神託
set の操作において、std::lower_bound(X.begin(), X.end(), t) と X.lower_bound(t) は目的が似ていますが、内部的な動作が異なるため、パフォーマンスにも違いがあります。
std::lower_bound(X.begin(), X.end(), t)
-
動作:
これはstd::setを範囲として扱い、線形イテレータアクセスを通じてバイナリサーチを行います。
std::setのデータは木構造（通常は赤黒木）で管理されているため、X.begin()からX.end()を使用して要素を取得するコストがかかります。
バイナリサーチ自体は ( O(\log n) ) の計算量ですが、イテレータ操作により要素を移動するコストが発生し、実際には遅くなることがあります。 -
計算量:
典型的には ( O(n) ) （イテレータを1つずつ進める必要があるため）。
X.lower_bound(t)
-
動作:
これはstd::set固有のメンバ関数で、直接内部の木構造にアクセスし、目的の値を探します。
赤黒木を利用した検索のため、不要なイテレータ操作を省略し、最短経路で目的の要素を取得します。 -
計算量:
( O(\log n) ) （std::setの木構造に依存）。
結論
-
X.lower_bound(t)の方が常に速いです。
理由は、std::lower_boundは汎用的なアルゴリズムで、std::setに特化した実装ではないため、イテレータ操作に余計なコストがかかります。 -
推奨:
std::setに対してはX.lower_bound(t)を使用してください。
補足
- 同様の理由で、
std::mapに対してもstd::lower_boundではなくmap.lower_boundを使用する方が効率的です。 - 必要なときに範囲アルゴリズム（
std::lower_bound）を使うのは、配列や他のコンテナ（例:std::vector）で効率的なソート済み探索を行いたい場合です。
反省点
解説動画 を拝見して、「同じことやってるつもりなんだけどなぁ
」とイライラしてましたが、「別に set じゃなくてもよくない？」と std::vectorでやろうとして WA を量産したのち、反省して std::set に変更してからの TLE 量産で、貴重な休日を浪費しました。
データ型選び大事。 （凡庸な結論）