AtCoder Regular Contest 098 E - Range Minimum Queries

E - Range Minimum Queries

問題概要

長さNの数列Aに対して，長さKの連続する部分を選びK個の要素の中で最小のものを削除する操作をQ回繰り返す． 削除される値の最大値と最小値の差を最小化する．

解法概要

Nはたかだか2000なので，最小値を決めうちしても良さそう．最小値を決めたとき，最大値と最小値の差を最小化するような最大値が$ O(n\log n) $とかでわかれば解けるはず．

最小値を決めうちするということは，最小値よりも低い値が消されないようにしないといけないので，最小値よりも低い値で元の数列を切ってしまえば，切った後の数列の中では小さい値から順に消すことができる．Q回のクエリで消せる値を列挙した配列の中でQ番目に小さい値と最小値の差を取れば，最小値を決めうちした時の最大値と最小値の差を最小化したものが求まる．あとは最小値の候補を変えながらこれをN回繰り返し，すべての場合の最大値と最小値の差の中で最小のものを出力すればよい．

実装について

• 最初は再帰で実装しようとして頭がこんがらがったのでfor文の入れ子で書いたら意外とすっきりした．再帰でもうまい実装はあるのだろうが．
• 2重のfor文の中でsortをしているので時間計算量が$ O(n^2 \log n) $に収まらないのではと心配になったが大丈夫そう．sort対象のvector bの長さmは，すべてのaa (aaはaの要素) の場合についてを合計してもnを超えることはない．なので全体として$ O(n^2 \log n) $には収まるはず．

ソースコード

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>

#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()

using namespace std;

typedef long long ll;

int main(){
    int n,k,q;
    cin >> n >> k >> q;
    vector<ll> a(n+1, 0LL);
    for(int i=0;i<n;i++) cin >> a[i];

    ll ans = LLONG_MAX;
    for(ll min_: a){
        vector<ll> removable, b;
        for(ll aa: a){
            if(aa < min_){
                int m = int(b.size());
                if(m >= k){
                    sort(all(b));
                    for(int i=0;i<min(m-k+1, q);i++) removable.push_back(b[i]);
                }
                b.clear();
            }else{
                b.push_back(aa);
            }
        }

        if(int(removable.size()) >= q){
            sort(all(removable));
            ans = min(ans, removable[q-1]-min_);
        }
    }
    cout << ans << endl;
}

感想

「決めた最小値よりも低い値で数列を分ける」という発想に至らなかった……． 解説動画を見て解法を知った後も実装方針 (再帰か，入れ子for文か) に悩んだ．