kmjp's blog

競技プログラミング参加記です

Codeforces #1133 : Div.1 A. Reverse and Double

そこそこの結果。
https://codeforces.com/contest/2279/problem/A

問題

整数列Aに対し、以下の処理を最大1回行える。

  • 部分列を指定し、その中の並びを反転したうえで2倍にする

隣接要素の差の絶対値の最大値を最小化したい。その時の値を求めよ。

解法

二分探索で解く。
解をv以下にできるか判定することを考える。

Aの初期状態で、隣接要素同士がvより大きな差がある箇所を列挙する。
vより大きな差がある場合、左右のどちらかは反転により値を差し替える必要がある。

  • 0か所:v以下が確定する。
  • 1か所:その1か所は、反転箇所の両端候補になるので、もう1か所の端を総当たりしチェックする。
  • 2か所:その2か所は、反転箇所の両端候補になるので、実際に反転させて確認する。
  • 3か所:v以下にできないことが確定する。
int T,N,A[303030];
int B[303030];

int ok(int v) {
	vector<int> V;
	int i,x,y;
	FOR(i,N-1) if(abs(A[i+1]-A[i])>v) V.push_back(i);
	
	if(V.size()==0) return 1;
	if(V.size()>2) return 0;
	if(V.size()==2) {
		x=V[0]+1;
		y=V[1];
		FOR(i,N) {
			B[i]=A[i];
			if(i>=x&&i<=y) B[i]*=2;
		}
		reverse(B+x,B+y+1);
		
		FOR(i,N-1) if(abs(B[i+1]-B[i])>v) return 0;
		return 1;
	}
	x=V[0];
	for(i=x+1;i<N;i++) {
		if(i>x+1&&abs(A[i]-A[i-1])*2>v) break;
		if(abs(A[x]-2*A[i])<=v&&(i==N-1||abs(2*A[x+1]-A[i+1])<=v)) return 1;
	}
	for(i=x;i>=0;i--) {
		if(i<x&&abs(A[i]-A[i+1])*2>v) break;
		if(abs(A[x+1]-2*A[i])<=v&&(i==0||abs(2*A[x]-A[i-1])<=v)) return 1;
	}
	
	return 0;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int ma=0;
		FOR(i,N) {
			cin>>A[i];
		}
		int ret=(1<<20)-1;
		for(i=19;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
		cout<<ret<<endl;
		
		
	}
}

まとめ

しょうもないミスで1WAしてしまったのもったいない。