Codeforces Global Round 17 : E. AmShZ and G.O.A.T.

まぁまぁ出来の良かった回。
https://codeforces.com/contest/1610/problem/E

問題

数列がterribleであるとは、以下を意味する。

• 数列の平均値より大きな値の要素数が、数列の平均値より小さな値の要素数より大きいこと

数列がbadであるとは、部分列にterribleなものを含むことをいう。

昇順に値が並んだ整数列Aが与えられる。
ここからいくつか要素を取り除き、Aをbadでないようにしたい。
最小何要素取り除けばよいか。

解法

badである条件は、階差数列が広義単調増加であることを意味する。
Aから要素を取り除いた時、先頭要素がA[i]とする。
この先頭要素を総当たりしよう。
次に来る要素を二分探索を繰り返し、以後階差数列が広義単調増加であるうち最小の要素を残すようにしていけばよい。
そうして何要素Aに残せるかを判定していく。

int T,N;
ll A[202020];

set<int> nex[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>A[i];
		}
		
		int ma=2;
		FOR(i,N) {
			if(i&&A[i]==A[i-1]) continue;
			int nex=lower_bound(A,A+N,A[i]+1)-A;
			if(nex==N) {
				ma=max(ma,N-i);
				continue;
			}
			int num=nex-i+1;
			while(1) {
				ll ne=A[nex]+A[nex]-A[i];
				nex=lower_bound(A,A+N,ne)-A;
				if(nex==N) break;
				num++;
			}
			ma=max(ma,num);
			
		}
		
		
		cout<<N-ma<<endl;
		
		
	}
}

まとめ

これはすんなり思いつけて良かった。