Codechef - Chef and K Segments [CHEFKO]
問題
n個の区間があり、i個目区間の左端はL[i]、右端はr[i]である
これらから好きな区間をk個選び、それら全ての共通区間の長さをスコアとする
スコアの最大値を求めよ
1 <= k <= n <= 10^5
1 <= L[i] <= r[i] <= 10^9
解法
スコアを二分探索すれば解ける
スコアをdにすることが出来るかの判定方法を考える
共通区間の左端右端はそれぞれ、n個の区間のどれかの左端右端と一致するはず
よって左端右端の候補はそれぞれn通りしかない
左端をL[i]とすると、
1) 左端がL[i]以下
かつ
2) 右端がL[i]+d以上
の区間がk個存在すれば良い
与えられる区間を左端の昇順にソートして左から順に1個ずつ見ていくことにすると、条件1を満たすのは今見ている区間と今まで見た区間だけになる
更にその中に条件2を満たすものが何個あるかを数えたい
これは降順priority_queueに今まで見た区間の右端の座標を入れていけばわかる
queue.top()が今の条件2を満たすまでpopし続け、その後のqueueのサイズが条件を両方とも満たすような区間の個数になる
区間は左端の昇順に並んでるから、見る区間を右にずらしていくと条件2は単調に厳しくなっていくため、一度popした要素は二度と使うことはない
O(n(logn)^2)で、TLが1sで0.93sかかってる
こういうやたら厳しいTLって極限まで定数倍高速化した愚直解とかbitsetで高速化みたいなのが間違って通らないためにやってんだろうけど、ちょっと定数倍が遅いくらいのまともな解法が落ちるよりはそっちのが不幸な人減らない？
int Q, n, k; pair<int,int> p[100100]; bool ok(int d) { priority_queue<int, vector<int>, greater<int> > q; rep(i,n) { q.push(p[i].second); while (!q.empty() && q.top()<p[i].first+d) q.pop(); if (k<=q.size()) return 1; } return 0; } signed main() { cin >> Q; while (Q--) { cin >> n >> k; rep(i,n) cin >> p[i].first >> p[i].second; sort(p, p+n); int l = 0, r = 1<<30; while (r-l>1) { int m = (l+r)/2; (ok(m) ? l : r) = m; } cout << l << endl; } }
