AtCoder Regular Contest 098 E - Range Minimum Queries

いやー、これは反省ですねえ。
つらいつらい。

にゃん

すこーしだけ丁寧に書きたい(願望)ので丁寧に私の思考をなぞっていきましょう。(未定)


問題を見て、最初に操作についてみてみるんですね。
ある連続したK個について操作を行った後、同じところにやろうとすると、実際は連続するK+1この中から一番小さい数字とその次の数字を取ることと同じだなあ、だとか。


こう操作を見ていくとちょっと思うんですよ。
「あー。これ sorted and sortedだなあ(違うけれど最近やったので)、DPしたいなあ(違うけれど)」
DPを探していくと
dp[i][j][k] := iからjまでk回操作を行った時の最小(最大)
とかできそうだなあ、O(n^4)とかになるなあ(ほんとか?)、遷移謎だなあ、ほんとにできるのかなあ??

無理そうですね、他のことを考えましょう、X-Yの話です。
X-Yを見るということは、最大と最小が必要なんですよ、n=2000なので、一回の探索がO(n log n)くらいまでなら最小または最大について探索すれば行けるのかなあ?(この感覚大事だよね、これはいい感じ)
となります。今回は最小を固定したときに最大がどうなるか~ってみるんですね。


さて、最小を決めた後、何が取れるかについてなんですが。
最小と決めたものより小さい数字は取りたくないのです。そのため最小と決めたものより小さいもののindexを覚えておき、今見ているものを含むk個の連続した数列がそれら(最小より小さいもの)を含まずにとれるかを見ていきます。これはいい感じにやるとO(n log n)くらいでできますね。


この操作は最小と決めたものから順にみていきたいのですが、ある数字が取れるとした際に同じ区間(indexで区切られた区間)にある他の数字が取れるかどうかを見るのに少しややこしい。例えばその区間から二個目の数字を取る時は区間の長さがk+1以上ないといけませんね。
結局その区間の右端の数字にその区間から今まで何個取ったかを記憶して置くことで対応しました。


ここら辺の実装は難しいですね、私が下手なだけなのかな?AOJするべきかな?実装苦手なんですよねえ。グダグダ言わずにやりましょう。

#include <bits/stdc++.h>
 
using namespace std;
 
#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define MOD 1000000007
 
typedef long long ll;
typedef pair<ll,ll> P;
 
int main(){
	ll n,k,q;
	cin >> n >> k >> q;
	vector<pair<ll,ll>> v;
	REP(i,n){
		ll tmp;cin >> tmp;
		v.PB(MP(tmp,i));
	}
	sort(ALL(v));
	ll ans = v[q-1].FI - v[0].FI;
	REP(i,n){
		set<ll> place;
		place.insert(-1);
		place.insert(n);
		vector<int> kazu(n+10);
		for(int j = 0;j <= i;j++)place.insert(v[j].SE);
		vector<ll> seica;
		for(ll j = i+1;j < n;j++){
			auto it = place.lower_bound(v[j].SE);
			ll tmpA = *it;
			it--;
			ll tmpB = *it;
			if(tmpA - tmpB - 1 - kazu[tmpA]>= k){
				seica.PB(v[j].FI);
				kazu[tmpA]++;
			}
		}
		
		sort(ALL(seica));
		if(seica.size() >= q)ans = min(ans,seica[q-1]-seica[0]);
	}
	
	cout << ans << endl;	
	
	return 0;
}

最近変数に困るとseicaとか使い始めていますね。seica便利(?)。seicaソートしなくてもよさそう。
区間から何個取ったかを管理する配列はkazuです、安直。



こんな感じで解けました~、とかいうと普通に見えますが、これ8WAくらい出しています。
一つの区間から複数個の数字を取る時の処理を考えてなかったんですね。ちゃんと詰めてから実装しましょう。
残り30分とかになってから一呼吸おいて改めて考え直したらそれが見つかりました。ダメダメではありましたがしっかり沼から抜け出せたのでよしとしません(?)、この癖は直しましょう。