🌊

ライブラリを用いた2分探索_ABC 334 D - Reindeer and Sleigh を理解し、忘れないようにする

2024/09/30に公開

https://atcoder.jp/contests/abc334/tasks/abc334_d

考察

Riをソートして累積和(今後これをAとする)を行い、 クエリーの値に対して2分探索を行う。
lower_boundの結果で取得するindexをjとする
2分探索により、A[j]がX以上かどうかの境界値を求められるので、Xを超えないギリギリの値を求める。
以下が実装した内容

lower_boundで実装を行う

lower_boundの仕様

2分探索ライブラリのlower_boundの仕様を記載する。
lower_boundは、ソートされた配列内で、key以上の要素の内の一番最初のイテレータを取得する。

実装

https://qiita.com/drken/items/97e37dd6143e33a64c8c#1-普通の二分探索から-stdlower_bound-へ

lower_boundの結果で取得するindexをjとする
lower_boundを使用すると上記の考察をコードに落とし込めるが、以下のような条件判定が必要になる。

  • A[j]とXが同じになる場合

    • jを出力する。
  • XがA[j]よりが小さい場合

    • lower_boundはA[j]のX以上の最小のindexを取得するので、この条件の場合j-1を出力する。
  • XがRiの合計より大きいとき、つまりX >= a.back()の場合

    • Rのサイズを出力する。
    • この場合、lower_boundだとa.back()を超える値を取得してしまい配列外参照になるのでlower_boundを使う前に判定を行う。
  • 以下が提出コード

https://atcoder.jp/contests/abc334/submissions/58158664

upper_boundで実装を行う。

upper_boundの仕様

ソートされた配列内で、keyより大きい要素の内の一番最初のイテレータを返す。

実装

lower_boundでは条件判定が多かったがupper_boundを用いるとかならずXより大きいA[j]のindex番号を取得できる。よってj-1を出力すれば回答になる。

回答コード

https://atcoder.jp/contests/abc334/submissions/58279601

Discussion