Codeforces Global Round 12 : F. The Struggling Contestant

Eより正答者が多い。
https://codeforces.com/contest/1450/problem/F

問題

N要素の整数列Aが与えられる。

1～NのPermutation Pのうち、A[P[i]]とA[P[i+1]]が一致しないようなものを作りたい。
そのさい、|P[i]-P[i+1]|＞1となるiの数がPのコストとなる。
条件を満たすPの最小コストを求めよ。

解法

Aが単一の値が過半数占める場合、条件を満たすことはできない。
そうでない場合、Aで同じ値が連続する場合は、そのままだと条件を満たさないので間に他の要素を入れる必要がある。
そこで、極力他の値で連続するところから1つ引っ張ってこよう。

int T,N;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		map<int,int> M;
		FOR(i,N) {
			cin>>A[i];
			M[A[i]]++;
		}
		int ng=0;
		FORR(m,M) if(m.second>(N+1)/2) ng=1;
		if(ng) {
			cout<<-1<<endl;
			continue;
		}
		M.clear();
		int sum=0;
		FOR(i,N-1) {
			if(A[i]==A[i+1]) {
				sum++;
				M[A[i]]++;
			}
		}
		int la=-1;
		FORR(m,M) if(m.second*2>sum) la=m.first;
		
		if(la==-1) {
			cout<<sum<<endl;
			continue;
		}
		int ret=0;
		int lef=sum-M[la];
		ret=2*lef;
		x=sum-2*lef;
		
		if(x&&A[0]!=la) ret++, x--;
		if(x&&A[N-1]!=la) ret++, x--;
		ret+=x*2;
		cout<<ret<<endl;
		
	}
}

まとめ

CGRのFの割には簡単。