なんとか解けて良かった。
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でもいい気がするな。