ABC 334 D - Reindeer and Sleigh を理解し、忘れないようにする

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