🌊
ライブラリを用いた2分探索_ABC 334 D - Reindeer and Sleigh を理解し、忘れないようにする
考察
lower_boundの結果で取得するindexをjとする
2分探索により、A[j]がX以上かどうかの境界値を求められるので、Xを超えないギリギリの値を求める。
以下が実装した内容
lower_boundで実装を行う
lower_boundの仕様
2分探索ライブラリのlower_boundの仕様を記載する。
lower_boundは、ソートされた配列内で、key以上の要素の内の一番最初のイテレータを取得する。
実装
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を使う前に判定を行う。
-
以下が提出コード
upper_boundで実装を行う。
upper_boundの仕様
ソートされた配列内で、keyより大きい要素の内の一番最初のイテレータを返す。
実装
lower_boundでは条件判定が多かったがupper_boundを用いるとかならずXより大きいA[j]のindex番号を取得できる。よってj-1を出力すれば回答になる。
回答コード
Discussion