Codeforces ECR #097 : E. Make It Increasing

割と難しめだった回？
http://codeforces.com/contest/1437/problem/E

問題

整数列Aが与えられる。
Aのうち、一部の指定された要素は値を変更できない。
その他の項目は、任意の整数に変更できる。

Aを単調増加するために、必要な処理回数の最小値を求めよ。

解法

Aを、値を変更できない箇所ごとに分割する。その分割した領域毎に問題の値を求めよう。
今Aの部分列A[x...y]において、A[x]とA[y]が値を変更できず、その間が変更できるとする。

• A[x]＞A[y]の場合は解なし。
• A[x]≦A[y]の場合、A[(x+1)...(y-1)]のうちA[x]未満またはA[y]より大きいものは、値を変更することが確定する。残りの要素については、できるだけ値を変更したくないのでLISを求めLISに含まれない要素のみ変更することとしよう。

int N,K;
int A[505050],B[505050];

vector<int> LIS(vector<int>& v) {
	int i,N=v.size();
	vector<int> dp(N,1<<30),id(N);
	FOR(i,v.size()) {
		id[i] = lower_bound(dp.begin(),dp.end(),v[i]+1) - dp.begin();
		dp[id[i]] = v[i];
	}
	int nl = *max_element(id.begin(),id.end());
	vector<int> ret(nl+1);
	FOR(i,N) if(id[N-1-i] == nl) ret[nl--] = v[N-1-i];
	return ret;
}

int hoge(int L,int R) {
	vector<int> C;
	int num=0;
	int i;
	for(i=L+1;i<R;i++) {
		if(A[i]<A[L]) num++;
		else if(A[i]>A[R]) num++;
		else C.push_back(A[i]);
	}
	if(C.size()) {
		int tc=C.size();
		num+=tc-LIS(C).size();
	}
	return num;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	A[0]=-1<<20;
	A[N+1]=1<<30;
	FOR(i,N) {
		scanf("%d",&A[i+1]);
		A[i+1]-=i;
	}
	B[0]=0;
	B[K+1]=N+1;
	FOR(i,K) scanf("%d",&B[i+1]);
	N+=2;
	K+=2;
	ll ret=0;
	FOR(i,K) if(i) {
		if(A[B[i]]<A[B[i-1]]) return _P("-1\n");
		ret+=hoge(B[i-1],B[i]);
	}
	cout<<ret<<endl;
}

まとめ

Eは余り難しくないな。本番もBやDよりすんなり解いてた。