Codeforces #335 Div1 A. Sorting Railway Cars

うーん、グダグダで前回稼いだレートを失ってしまった。
http://codeforces.com/contest/605/problem/A

問題

1～Nのpermutationが与えられる。
これから一部の要素を任意の数列の先頭か末尾に移動することができる。

数列を1～Nと昇順にするのに必要な要素の移動数を求めよ。

解法

一見LISを求めれば良さそうだが、間に要素を挿入することはできないのでLISは不可。
PretestはLISで通るようになっており、自分はそれでResubmitしたけど代わりに3Hackできた。

中に挿入は出来ないけど、余計なものを外に出すことはできるので、連番が昇順に並んでいる最大要素数を求めれば残す要素がわかる。

int N;
int num[101010],P[101010];

void solve() {
	int i,j,k,l,x,y; string s;
	
	int ma=0;
	cin>>N;
	FOR(i,N) {
		cin>>x;
		num[x]=num[x-1]+1;
		ma=max(ma,num[x]);
	}
	cout<<(N-ma)<<endl;
	
	
}

まとめ

自分以外に赤い人もLISやらかしてたし、いいひっかけ問題。