Pinely Round 5 : D. Locked Out

不参加だった回。
https://codeforces.com/contest/2161/problem/D

問題

整数列Bがgoodであるとは、i＜jかつB[i]+1=B[j]となる(i,j)が存在しないことを指す。

N要素の整数列Aが与えられる。
いくつかの要素を取り除いてAをgoodにするには、最小何要素取り除けばよいか。

解法

(A[i],i)のペアを考え、前者を昇順、後者を降順となるように並べ、以下を考える。

f(i) := 上記の順番で小さい順にAの残すか考えたとき、iまで考えたときにi番目を残す場合の最大要素数

(A[i],i)を置いていい条件は、手前にj=A[i]-1かつj＜iとなる(A[j],j)が存在しないことである。
よって上記以外のjについてf(i) = max(f(j))+1となる。

int T,N,A[303030];
vector<int> cand[303030];
int dp[303030];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cand[i].clear();
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			cand[A[i]].push_back(i);
		}
		int pre=0;
		FOR(i,N) {
			reverse(ALL(cand[i]));
			int cur=pre;
			if(i) {
				x=0;
				FORR(a,cand[i]) {
					while(x<cand[i-1].size()&&cand[i-1][x]>a) {
						cur=max(cur,dp[cand[i-1][x++]]);
					}
					cur=dp[a]=cur+1;
				}
				FORR(a,cand[i-1]) pre=max(pre,dp[a]);
			}
			else {
				cur=0;
				FORR(a,cand[i]) {
					dp[a]=++cur;
				}
			}
		}
		int ret=0;
		FOR(i,N) {
			ret=max(ret,dp[i]);
		}
		cout<<N-ret<<endl;
		
	}
}

まとめ

わかってしまうとすんなりなのだけどね。