CSAcademy Round #50 : E. Min Swaps

割とすんなり思いつけた。
https://csacademy.com/contest/round-50/task/min-swaps/

問題

偶数Nに対し、1～Nのpermutationである数列Aが与えられる。
Aに対し、任意の２要素のSwapを繰り返し、隣接要素の差の絶対値の総和を最大にしたい。

最小何回のSwapで達成できるか。

解法

サンプルが親切。
条件を満たす数列は以下のいずれかである。

• 先頭がN/2で、以後偶数番目にN/2より大きく、奇数番目にN/2より小さい値が来る。最後は(N/2)+1。
• 先頭が(N/2)+1で、以後奇数番目にN/2より大きく、偶数番目にN/2より小さい値が来る。最後はN/2。

よって両方の候補に対し、それを満たすような最小swap回数を求めればよい。

int T;
int N;
int P[101010];
int Q[101010];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		int L,R;
		FOR(i,N) cin>>P[i];
		int mi=1<<30;
		FOR(i,2) {
			FOR(x,N) {
				if(i==0) Q[x]=P[x];
				else Q[x]=P[N-1-x];
				if(Q[x]==N/2) L=x;
				if(Q[x]==N/2+1) R=x;
			}
			int cost=0;
			if(L!=0) {
				cost++;
				swap(Q[0],Q[L]);
				if(R==0) swap(L,R);
				else L=0;
			}
			if(R!=N-1) {
				cost++;
				swap(Q[R],Q[N-1]);
			}
			
			for(x=1;x<N-1;x+=2) if(Q[x]<=N/2) cost++;
			mi=min(mi,cost);
		}
		cout<<mi<<endl;
		
	}
}

まとめ

サンプルがこんな丁寧じゃなければ解ける人減ってそう。