2022-01-25 第八回 アルゴリズム実技検定 (PAST) L - K番目の絶対値 を解いた
第八回 アルゴリズム実技検定 (PAST) L - K番目の絶対値 を解いた。
問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_l
「連続した空でない部分列の総和」は累積和の 2 点の差で求める。 2 点の全探索は O(N^2) で N <= 3*10^5 からこれは間に合わない。すべてのスコアを求めて K 番目を求めることはできない。
こういう場合はスコアを二分探索してみる。スコア x を決め打ちしたときに x よりも小さいスコアの個数が K 個未満と以上で二分探索すれば K 個以上の側が答えになる。
……ここまで考察したのだけど K 個以上の位置を計算量を下げつつ探索する方法が分からなかった。
解説: https://atcoder.jp/contests/past202109-open/editorial/2398
考察した範囲では正しかった。 |S_j - S_i| <= x (i < j && i != j) な 2 点を探索すれば良く、もう順序は問題にならないのでソートしてしまって良い。これに気づかなかった。ソートしてしまえば単に s[i+1..].upper_bound(&(s_i + x)) の和で個数が求められる。
解説では尺取法を使っているが各値に対して upper_bound の二分探索でも各探索が O(N) から O(NlogN) になる程度なので間に合う。
これはがんばれば解けたかもしれない……。ちなみに INF の誤りと探索する値の誤りなどで 2 WA している。
提出: https://atcoder.jp/contests/past202109-open/submissions/28796885
今日のコミット。