Range Minimum Queries [AtCoder Regular Contest 098 E]

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

考察

1. Nの制約が小さい
2. 何かを全探索したいが、どれが効率的だろうか
3. 最小のものを取り除いていくので、最小値Yを全探索すれば良さそう
4. A[i]＜Yのものは取れないので、数列がいくつかの数列に分割される
5. 各数列から貪欲に小さい数を取って行けばXが最小化できる
6. Yを全探索して、貪欲に取っていくのにpriority_queueを使えばO()N^2logN)で大丈夫そう

解法

https://beta.atcoder.jp/contests/arc098/submissions/2573067

考察の通り実装する。
ダメな要素があって、いくつかの部分数列に分解するには、ダメな要素の添字を集めた配列を用意し、
その要素間で処理を行っていくのが良い。
番兵として先頭に-1,末尾にNを置いておくとコードがシンプルになる。
各部分数列について個数がK個未満になるまで貪欲に最小値を取ってくる。
全ての部分数列から集めた最小値の先頭Q個を採用してXを最小化し、X-Yの最小値を答えとする。

template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;
int N, K, Q, A[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K >> Q;
    rep(i, 0, N) cin >> A[i];
 
    int ans = inf;
    rep(y, 0, N) { // Y=A[y]として取っていく
        int Y = A[y];
 
        vector<int> v;
        v.push_back(-1);
        rep(i, 0, N) if (A[i] < Y) v.push_back(i);
        v.push_back(N);
 
        int n = v.size();
        min_priority_queue<int> qu;
        rep(i, 0, n - 1) {
            int l = v[i] + 1;
            int r = v[i + 1];
 
            // [l,r)
            min_priority_queue<int> buf;
            rep(i, l, r) buf.push(A[i]);
            while (K <= buf.size()) {
                qu.push(buf.top());
                buf.pop();
            }
        }
 
        int X = Y;
        int q = Q;
        while (0 < q && !qu.empty()) {
            chmax(X, qu.top());
            qu.pop();
            q--;
        }
 
        if (q == 0) chmin(ans, X - Y);
    }
    cout << ans << endl;
}