Codeforces #778 : E. Arithmetic Operations

DよりEの方が簡単に解いてるな。
https://codeforces.com/contest/1654/problem/E

問題

N要素の整数列Aが与えられる。
このうち何要素かを任意の値に書き換え、全体を等差数列となるようにしたい。
最小何要素書き換える必要があるか。

Nの上限は10^5であり、Aは1以上10^5以下である。

解法

N,Aの範囲が狭いことを利用し、以下をそれぞれ試す。

• 公差の絶対値を√maxA程度まで総当たりする
• 公差がそれ以上である場合、書き換えずに済むのは高々√N要素である。よって各要素を左端としたとき、右端をそこからO(√N)要素程度まで総当たりし、公差が一致するものが多い要素を選ぶ。

int N,A[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	int ma=min(N,2);
	
	FOR(j,2) {
		
		for(int d=0;d<=350;d++) {
			vector<int> B;
			FOR(i,N) B.push_back(A[i]-i*d);
			sort(ALL(B));
			int pre=-1<<30;
			int cnt=0;
			FORR(b,B) {
				if(b!=pre) cnt=0;
				cnt++;
				pre=b;
				ma=max(ma,cnt);
			}
		}
		
		FOR(i,N) {
			vector<int> B;
			for(l=1;l<=350&&i+l<N;l++) {
				if((A[i+l]-A[i])%l==0) B.push_back((A[i+l]-A[i])/l);
			}
			sort(ALL(B));
			int pre=-1<<30;
			int cnt=0;
			FORR(b,B) {
				if(b!=pre) cnt=0;
				cnt++;
				pre=b;
				ma=max(ma,cnt+1);
			}
		}
		
		
		reverse(A,A+N);
	}
	
	cout<<N-ma<<endl;
	
}

まとめ

すんなり解けてよかったね。