kmjp's blog

競技プログラミング参加記です

Mail.Ru Cup 2018 Round 2 : E. Segments on the Line

なんとか解けて良かった。
http://codeforces.com/contest/1055/problem/E

問題

N要素の整数列A[i]と、整数列の部分列S個が与えられる。
S個中M個の部分列を選び、その和集合からなるmultisetを考える。
そのmultiset内でK番目に小さい要素を最小化せよ。

解法

multiset中ある整数VをK個以上含められるようなVの最小値を求めればよい、と考えるとVを二分探索することで解を求められる。
そうすると、A[i]をV以下かV以降かで1/0に分類したとき、multiset中に1をK個以上含められるか?という問題に答えられれば良い。

以下を考える。
dp(a,b) := A[0...a]の区間にあるb個の部分和を選択したとき、その中の1の数
dp(n-1,x)≧KとなるM以下のxが存在すれば、上記条件を満たすことになる。

dp(a,b)がわかっているとき、以下の条件分岐を取れる

  • A[a+1]をmultisetに含めない場合、dp(a+1,b)はdp(a,b)以上
  • S個の部分列のうち左端が(a+1)以下の物のうち、右端の最大値をcとするとdp(c,b+1)はdp(a,b)+(A[(a+1)..c]の範囲の1の数)以上
int N,S,M,K;
int A[2020],B[2020];
int L[2020],R[2020];
vector<int> V;

int MR[2020];
int dp[1600][1600];

int ok(int v) {
	int i,j;
	FOR(i,N) B[i+1]=B[i]+(A[i]<=v);
	
	ZERO(dp);
	FOR(i,N) {
		FOR(j,M) {
			if(MR[i]>i) {
				dp[MR[i]][j+1]=max(dp[MR[i]][j+1],dp[i][j]+B[MR[i]]-B[i]);
				if(dp[MR[i]][j+1]>=K) return 1;
			}
			dp[i+1][j]=max(dp[i+1][j],dp[i][j]);
		}
	}
	return 0;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>S>>M>>K;
	FOR(i,N) {
		cin>>A[i];
		V.push_back(A[i]);
	}
	FOR(i,S) {
		cin>>L[i]>>R[i];
		for(j=L[i]-1;j<R[i];j++) MR[j]=max(MR[j],R[i]);
	}
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	if(ok(V.back())==0) return _P("-1\n");
	
	int ret=V.size()-1;
	for(i=12;i>=0;i--) {
		if(ret>=(1<<i) && ok(V[ret-(1<<i)])) ret-=1<<i;
	}
	cout<<V[ret]<<endl;
}

まとめ

これはDiv1 1750pt相当とあるけど、1250~1500ptでもいい気がするな。