ARC 098 E Range Minimum Queries

問題概要

長さ N の数列 A と整数 K が与えられる。この配列に、以下の操作を Q 回行います。

長さ K の連続する部分列を 1 つ選ぶ。そして、選んだ部分列に含まれる K 個の要素のうち最小のもの（複数ある場合はその中で好きなものを 1 個）を取り除く。

Q 回の操作で取り除いた要素の最大値、最小値をそれぞれ X, Y としたときに、X−Y を最小化せよ。

制約

1 <= K <= N <= 2000
1 <= Q <= N - K + 1

解法

最小値を固定すると一気に考えやすくなる。最小値となる index を固定すると、それを含む区間は採用できなくなる。また際立った特徴として、最小値を固定したならば最大値は貪欲に小さくすればよくなる。

最小値を固定した index ごとに配列全体を区切ると、いくつかの区間に分かれる感じになる。それぞれの区間については、大きい方から見て K-1 個を除いた数を取り出せる。こうしてかき集めてきた数のうち、Q 番目の値を求めればよい。

O(N² logN)

#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <utility>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <unordered_map>
using namespace std;

#define REP(i, s) for (int i = 0; i < s; ++i)
#define ALL(v) (v.begin(), v.end())
#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
#define EACH(i, s) for (__typeof__((s).begin()) i = (s).begin(); i != (s).end(); ++i)

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ EACH(it, P) { s << "<" << *it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ EACH(it, P) { s << "<" << it->first << "->" << it->second << "> "; } return s << endl; }

int N, K, Q;
vector<long long> A;

int main() {
    while (cin >> N >> K >> Q) {
        A.resize(N);
        for (int i = 0; i < N; ++i) cin >> A[i];

        long long res = 1LL<<60;
        for (int i = 0; i < N; ++i) {
            vector<long long> vec;
            vector<long long> tmp;
            for (int j = 0; j < N; ++j) {
                if (A[j] < A[i]) {
                    if (tmp.size() >= K) {
                        sort(tmp.begin(), tmp.end());
                        for (int k = 0; k < (int)tmp.size() - (K-1); ++k) {
                            vec.push_back(tmp[k]);
                        }
                    }
                    tmp.clear();
                }
                else {
                    tmp.push_back(A[j]);
                }
            }
            if (tmp.size() >= K) {
                sort(tmp.begin(), tmp.end());
                for (int k = 0; k < (int)tmp.size() - (K-1); ++k) {
                    vec.push_back(tmp[k]);
                }
            }
            
            //cout << i << ", " << A[i] << ": " << vec << endl;
            
            sort(vec.begin(), vec.end());
            if (vec.size() >= Q) {
                chmin(res, vec[Q-1] - vec[0]);
            }
        }
        
        cout << res << endl;
    }
}