Codeforces Global Round 20 : F1. Array Shuffling

良くもなく悪くもなく。
https://codeforces.com/contest/1672/problem/F1

問題

整数列Aが与えられる。
この数列のうち、2要素のswapを繰り返し、数列Bを作ったとする。

Bが与えられたとき、swap回数が最大となるAを1つ求めよ。

解法

互いに異なる要素がn個あったとき、それらの位置を1個シフトすれば、swapをn-1回行わないといけなくなる。
そこで、そのような互いに異なる要素をグループにしていこう。

ある要素kがC[k]個あったら、グループ1～C[k]に1個ずつkを配置すればよい。

int T,N,A[202020],B[202020];
int C[202020];
vector<pair<int,int>> E[202020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		
		FOR(i,N+1) C[i]=0, E[i].clear();
		
		FOR(i,N) {
			cin>>A[i];
			assert(1<=A[i]&&A[i]<=N);
			E[++C[A[i]]].push_back({A[i],i});
		}
		
		for(i=0;i<=N;i++) {
			x=E[i].size();
			sort(ALL(E[i]));
			FOR(j,x) B[E[i][j].second]=E[i][(j+1)%x].first;
		}
		
		
		FOR(i,N) cout<<B[i]<<" ";
		cout<<endl;
		
		
	}
}

まとめ

本番なんか妙に手間取ってるな…。