Codeforces #768 : Div1 B. Range and Partition

4完でこの順位か…。
https://codeforces.com/contest/1630/problem/B

問題

N要素の整数列Aと、正整数Kが与えられる。
以下を満たす整数対(x,y)のうち、y-xを最小化でする1例を求めよ。

• AをK個の部分列に分ける。各部分列において、[x,y]に含まれる要素数は、それ以外の要素より多い。

解法

まず(x,y)を求めよう。
[x,y]に含まれる要素数が(N+K)/2以上あれば、条件を満たす分割が可能である。
よって、尺取り法の要領で、xを総当たりしながら対応するyを求めよう。

(x,y)が求まったら、Aを分割するだけ。[x,y]に含まれる要素が過半数になった時点で切っていこう。

int T,N,K;
int A[202020];
int num[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		FOR(i,N+1) num[i]=0;
		FOR(i,N) {
			cin>>A[i];
			num[A[i]]++;
		}
		int mi=1<<20;
		for(i=1;i<=N;i++) {
			num[i]+=num[i-1];
		}
		for(int L=1,R=0;L<=N;L++) {
			while(R<=N&&2*(num[R]-num[L-1])<N+K) R++;
			if(R>N) break;
			if(R-L<mi) {
				mi=R-L;
				x=L,y=R;
			}
		}
		vector<pair<int,int>> V;
		FOR(i,N) {
			j=(x<=A[i]&&A[i]<=y);
			if(V.size()&&V.back().first!=j) V.pop_back();
			else V.push_back({j,i});
		}
		int pre=1;
		vector<pair<int,int>> ret;
		FOR(i,K-1) {
			ret.push_back({pre,V[i].second+1});
			pre=V[i].second+2;
		}
		ret.push_back({pre,N});
		
		cout<<x<<" "<<y<<endl;
		FORR2(a,b,ret) cout<<a<<" "<<b<<endl;
		
		
	}
}

まとめ

本番は意外にすんなり解いてるな。