yukicoder : No.711 競技レーティング単調増加

こういうのすんなり解けるといいんだけども。
https://yukicoder.me/problems/no/711

問題

N要素の正整数列Aが与えられる。
いくつかの要素を書き換え、Aを正整数からなる狭義単調増加列にしたい。
最小何個要素を書き換えればよいか。

解法

Aに任意の要素が取れるなら話は簡単である。
(0-indexedの場合) B[i] = A[i] - (i+1)で構成される数列Bに対し、Bを単調増加にすればいいのでN-|LIS(B)|が解となる。
ただし今回の場合B[i]は0以上でなければならない。

そこで、B[i]のうち負になるものは「そもそも書き換えなければいけないもの」としてLIS構成の際に考慮しないものとする。
よって、N-|LIS(Bのうち非負のもの)|が解。

int N;
int A[202020];
int V[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	for(i=0;i<=N+1;i++) V[i]=1<<30;
	int ma=0;
	for(i=1;i<=N;i++) {
		cin>>x;
		x-=i;
		if(x<0) continue;
		y=lower_bound(V,V+N+1,x+1)-V;
		V[y]=x;
		ma=max(ma,y);
	}
	
	cout<<N-(ma+1)<<endl;
}

まとめ

シンプルな解法だね。