Codeforces ECR #039 : G. Almost Increasing Array

これあと少し時間があれば本番に解けたのに…。
http://codeforces.com/contest/946/problem/G

問題

N要素の整数列Aが与えられる。
ここから1つ要素を取り除いたあと、いくつかの要素を書き換えてこの整数列を増加列にしたい。
任意の要素を取り除けるとするとき、書き換えるべき要素数は最小いくつか。

解法

狭義単調増加の条件を広義単調増加の条件に置き換えるテクとして、A'[i] = A[i]-iで置き換えた数列を考えるテクがある。
ただ今回1つ要素を取り除けるので、取り除いた要素より後ろはA'[i] = A[i]-(i-1)で置き換えることになる。

よって最初から２通り数列を作っておこう。
B[i]=A[i]-i
C[i]=A[i]-(i-1)

i番目を取り除いた場合のケースを順次総当たりする。
B[0..(i-1)]とC[(i+1)...(N-1)]を連結した数列におけるLISが求まれば、LISに含まれない要素が置き換える要素となる。
B[0..(i-1)]のLISをP、C[(i+1)...(N-1)]を反転したもののLDSをQとする。

P[x]≦Q[y]である場合、B[0..(i-1)]とC[(i+1)...(N-1)]を連結した数列におけるLISの長さは*1である。
よって各xに対し、P[x]≦Q[y]となる最小のyを求めることを考えよう。
これはx毎にyを二分探索すればよいが、i毎に毎回それを行うとTLEする。
ただ、iを1つずつずらした場合、P,Qはそれぞれ1要素しか変化しないので、変化したP[x]に対するy、およびQ[y]に対するxを求めればよい。

iを1つずつ増加させる場合、B[0..(i-1)]に対するPはLISの構築手順をそのまま使うだけで生成できる。
一方QはC[(i+1)...(N-1)]が段々短くなるのでそうはいかない。
そこでQはまずiを小さくする向きにLDSを構築していき、その際Qの更新前後の値を覚えるようにしよう。
そうするとiを大きくした際に更新を巻き戻すことでQを得られる。

int N;
int A[202020];
int B[202020];
int C[202020];
int L[202020],R[202020];
int pos[202020],preR[202020];

int best=0;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		B[i]=A[i]+(N-1-i);
		C[i]=(1<<30)-(A[i]+(N-i));
	}
	FOR(i,N+5) L[i]=R[i]=(1<<30);
	
	for(i=N-1;i>=1;i--) {
		pos[i]=lower_bound(R,R+(N+1),C[i]+1)-R;
		preR[i]=R[pos[i]];
		R[pos[i]]=C[i];
		best=max(best,pos[i]+1);
	}
	int prex;
	FOR(i,N) {
		x=lower_bound(L,L+(N+1),B[i]+1)-L;
		L[x]=B[i];
		best=max(best,x+1);
		if(i<N-1) {
			R[pos[i+1]]=preR[i+1];
			y=0;
			for(j=20;j>=0;j--) if(y+(1<<j)<=N && ((1<<30)-R[y+(1<<j)-1])>=L[x]) y+=(1<<j);
			best=max(best,x+1+y);
			
			x=pos[i+1];
			y=0;
			for(j=20;j>=0;j--) if(y+(1<<j)<=N && ((1<<30)-R[x])>=L[y+(1<<j)-1]) y+=(1<<j);
			best=max(best,x+1+y);
			
			
		}
	}
	cout<<max(0,N-1-best)<<endl;
}

まとめ

LIS/LDSの構築を巻き戻すテクが思いつけたのは良かった。

*1:x+1)+(|Q|-y