CPC013
CIST Private Contest 第13回目
t6o_o6t.icon
普通に遅刻
愚直に、NとMで2重ループを回して探索するとTLEになるはず。 驚異の2205 ms新人博士.icon
ただ、一方だけでループをする分には問題なさそうという感。
問題のゴールは、価値の和の最大値。そして、価値の差については$ |A_i - B_j|\le D。 まずは贈り物を価値でソートしたい。
例えば、この入力を考える
code: example_impartial_gift.py
2 3 2
3 10
2 5 15
3から見ると、差が2以下になる範囲とは、$ 1 \le B_i \le 5だね
したがって、ソート済み数列$ B_iを、値1と値5でそれぞれ二分探索することで、条件を満たす$ B_iの範囲を得られる
次に重要なのは、どのように和の最大値を取るか。
これは一番最後のを取ればよい。
つまり、先の例で値1の二分探索は不要ではないか。
必要といえるのは、値1以上がそもそも存在しない場合だが、それだと条件を満たす$ B_iも存在しない。
いや、必要だ
値5の二分探索だけをして、かつそのindex（または一個前）の$ B_iとの和を計算すればよい。
これであとは、すべての$ A_iに対して同じ処理を行えばよい。
方針は立った。あと10分で実装できるか。
不安だ
間に合わないな・・・
実装速度が足らない
疑問点
10から見るとどうか
$ 8 \le B_i \le 12
ゆえに、条件を満たすものは存在しない、が
$ a-D \le B_\alphaを満たすものと$ B_\beta \le a + Dを満たすものがどこか知りたい
ここでは、α = 2, β=1
2 5 15では、8を超えるのは15が最初
8を入れるとしたら2番目
bisect_leftも2を返す
つまり、$ \alpha \gt \betaになるとだめということ？
$ \alpha = \betaの場合はどうだろう？
それはいいと思う
$ a-D\le B_\alphaの条件をどう表現するか。
8で二分探索すると、多分カーソルが1個左
Streakが途切れちゃうからAC.iconしないといけない こういう感覚は久しぶり
かなりもやもやする
要は条件を満たす要素が存在するのかを知りたい
実装できない
解説を読もう
方針はこの解説と同じ
maxを使うと短くて良いな
bisect_rightかな
2 5 5 15
5が最小であるときは、範囲は1（bisect_leftに5を渡した戻り値）から右となる
5が最大のときは、範囲は3（bisect_right）の1個前から左
12が最小のときは、範囲は3（bisect_leftに12を渡した戻り値）の次の要素から右
12が最大のときは、範囲は3の
1. bisect_left
2. 要素の存在確認
3. 存在していればその要素
4. 存在しなければその次の要素からが範囲
このindexを$ \alphaとする
5. bisect_right
6. 1個前を見る
7. 要素の存在確認
8. 存在していればその要素
9. 存在しなければその前の要素から前が範囲
このindexを$ \betaとする
ここで、$ B_iが条件を満たすような任意の$ iで、$ \alpha \le i \le \betaが必要
したがって$ \alpha \le \beta
$ \alpha \gt \betaは許されない
18が最大のときは
18が最小のときは
分かりました
1. bisect_rightをします。
2. 返ってくる値は -1します。
-1した値を取る理由
bisect_right実行時
要素が存在した場合
リスト1 2 3 4に対して2で探索したとき、返ってくるのは2。
実際に2があるのは1だから-1する必要がある。
存在しない場合
リスト1 3 4に対して2で探索したとき、返ってくるのは1。
この場合は0を返してほしいので-1する必要がある。
3. 当該要素がa + D以下であることを調べる。
範囲の最初の要素はしらべなくてもこの条件を調べればよいと考えた。
4. 条件を満たすなら和を計算する。以降同様。
AC.icon！！
Pythonの二分探索ちょっと分かった。