Codeforces #278 Div1 B. Strip

本番MaximumとMinimumを間違えた…。
http://codeforces.com/contest/487/problem/B

問題

N要素の整数列A[i]が与えられる。
この数列を、以下の条件を満たす複数の連続部分列に分けたい。

• 各部分列の要素数はL以上である。
• 各部分列内の最大値と最小値の差はS以下である。

最小で何個の部分列に分けることができるか。

解法

まず前処理として各要素を左端とするような部分列では右端を最大どこまで広げられるかを求める。

setにA[i]の値を格納しつつ尺取法を行えばよい。
setにA[i]を追加したのち、set中の最大値A[x]と最小値A[y]の差がSを超える場合、xとyの小さい方をsetから取り除き、取り除いた方A[x]またはA[y]の右端はA[i-1]だと分かる。

次に、A[i]～A[N-1]までの条件を満たす部分列数をSegTreeに入れ、i=N-1からi=0まで逆順でDPしていく。
A[i]を左端とする部分列では、右端はi+L-1と前処理で求めた値の範囲にあるので、その中の部分列数の最大値をSegTreeから求めればよい。

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=1000000;
	V comp(V l,V r){ return min(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};

int N,S,L;
ll A[100005];
set<pair<ll,int> > SS;
int RR[100005];
int ret[100005];
SegTree_1<int,1<<18> st;

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N>>S>>L;
	
	int fin=0;
	FOR(i,N) {
		RR[i]=N;
		cin>>A[i];
		SS.insert(make_pair(A[i],i));
		while(SS.rbegin()->first - SS.begin()->first>S) {
			if(SS.begin()->second<SS.rbegin()->second) j=SS.begin()->second, SS.erase(SS.begin());
			else j=SS.rbegin()->second, SS.erase(*SS.rbegin());
			for(;fin<=j;fin++) RR[fin]=i;
		}
	}
	
	MINUS(ret);
	ret[N]=0;
	st.update(N,0);
	
	for(i=N-1;i>=0;i--) {
		ret[i]=1000000;
		l = i+L;
		r = RR[i];
		if(l>r) continue;
		j = st.getval(l,r+1);
		if(j>=0) ret[i]=1+j, st.update(i,ret[i]);
	}
	if(ret[0]>=1000000) cout << -1 <<endl;
	else cout<<ret[0]<<endl;
}

まとめ

本番あっさり解けたと思ったのに、maxとminを間違えて落とすとはもったいない。