ARC098 E Range Minimum Queries

問題文

https://beta.atcoder.jp/contests/arc098/tasks/arc098_c

 

消去する数の最大値-最小値を最小化しろ,と言われているので,どちらかを固定すると簡単になりそう.最小値をXに固定すると,Xより小さい数を含むような区間は選べず,含んでいない区間は好きに選べる,という状況になるので最小値を固定することにする.

Xを固定すると,元の区間はいくつかのX以上の数だけを含む小区間に分割される.今,最小値が固定されているので消去する数の最大値を最小化する問題になり,元の問題よりは簡単になった.

自分はここでにぶたんをすることを思いついた.更に消去する数の最大値Yを固定したとき,各小区間から消せる数の個数は(小区間内のY以下の数の個数)と(区間の長さ-K+1)のminになる(ただし区間の長さがK未満のときは1個も消せない).よって,各小区間についてこれを計算し,その和がQ以上ならば最大値をY以下に出来,そうでないなら出来ないことがわかるのでにぶたん.全体O(N^2logN)でとけた.

想定は,小さい方から順に数を消していくことが可能であることに注目し,各小区間内で小さい方から(区間の長さ)-K+1個の数を選んできたものを集め,その全体でQ番目に小さい数が最大値になるというものだった.ソートにO(NlogN)かかってこれも全体O(N^2logN).

 ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = 1000000007LL;
ll A[2000];
int main() {
    ll N, K, Q;
    cin >> N >> K >> Q;
    ll ma = 0;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        ma = max(ma, A[i]);
    }
    ll ans = 1 << 30;
    for (int i = 0; i < N; i++) {
        ll l = A[i] - 1, r = ma + 1;
        bool ok = 0;
        while (r - l > 1) {
            ll m = (l + r) / 2;
            ll cnt = 0;
            ll len = 0;
            ll sum = 0;
            for (int j = 0; j < N; j++) {
                if (A[j] < A[i]) {
                    sum += min(cnt, max(len - K + 1, 0LL));
                    len = 0;
                    cnt = 0;
                }
                else {
                    len++;
                    if (A[j] <= m) cnt++;
                }
            }
            sum += min(cnt, max(len - K + 1, 0LL));
            if (sum >= Q) r = m, ok = 1;
            else l = m;
        }
        if (ok) ans = min(ans, r - A[i]);
    }
    cout << ans << endl;
}