今日の精進 2020/06/02
51回目
— pitsu (@pitsu_kyo_pro) 2020年6月2日
ABCの3完
Educational Codeforces Round 17https://t.co/SNBb14fSdk
A:これ計算量大丈夫なのか....sqrt(10^15)....大丈夫やんけ
kが10^9でも約数がそんなにあるものないやんけ....はぁ....
B:aを全部やってbを全部やって余ったものをcで小さいものから
使っていく
c:左から使える範囲をposで求めていって右から使える範囲をposで求めていって左で使えるまで使ったとき右でどれだけ使えるかを二分探索していく
bより大きいサイズが来たときやばい(3WA+1時間吸われた)
青diffバチャ
ABの2完
A:こういうのはとりあえず折れ線で考える
a-bが負になるやつは状態を下げれるから先に使いたいよね
なので先にこいつら使う
使う順番は最大値が大きくならないようにしたいからaが小さいものを優先して使う
a = bはa-b使い切った後に使うのが一番よさそう（他の場所渋くない？
a-bが正になるやつの処理困った
最終地点考えたとき最後に使うやつは上に飛び出てほしくない
なのでbが大きいやつを先に使うか～～
->AC
a-bが正になるやつの処理雑すぎたので解説ちゃんと読む
B:各地点iでセグ木で最大値を左側、右側で調べて二分探索
二分探索でj番目とiの間の最大値はh[i]であればその場所はokダメならngにしてやる（めぐる式
https://kenkoooo.com/atcoder/#/contest/show/9819ad78-8f0d-4490-986f-0b12d6a96e9d
さっきのバチャの復習
僕が考えたこと
今見てる地点のものが最初に出せないならそれ以降のやつも絶対最初に出せない
なのでそれ以前のうちどれか一つを出さなきゃいけない
それまで見てたものの個数を掛け合わせる（以前に引いたものがあったらそれはカウントしない）
添え字で頭崩壊（悲しい
この記事が僕のやりたいことをきれいに実装しててよかった
