Codeforces #252 Div2 D. Valera and Swaps

ちょっとややこしいけど面白い問題。
http://codeforces.com/contest/441/problem/D

問題

1～NのpermutationであるP[i]が与えられる。
これらのP[i]の２要素をswapする処理を何度か繰り返すと1～Nの昇順配列になる。
この時、必要な最小swap回数をf(P)とする。

配列P[i]と数Mが与えられる。
P[i]を何度かswapし、f(P')=Mとなるような配列P'にするswap手順のうち、回数最小かつ辞書順最短のものを答えよ。

解法

まず、f(P)の求め方を考える。
Pを1-indexとして、i→P[i]→P[P[i]]→P[P[P[i]]]…という順列を考えると、最長Nの巡回列となる。
この事実より、まずPの要素をこれら巡回列群に分解する。
この手順はDFSでも良いし、Union-Findでも良い。

長さqの巡回列は、最短q-1回のswapでそれぞれ元の位置(P[i]=i)に戻すことができる。
よって各巡回列について(要素数-1)の和がf(P)となる。これはN-(巡回列の数)とも一致する。

ここで：

• f(P)=Mならこれ以上何もしなくてよい。
• f(P)
• f(P)>Mならf(P')がf(P)より小さくなるようにしたい。f(P')が小さくなるには、巡回列の数を増やせばよい。もともと同じの巡回列にある２要素をswapすること、その巡回列を２つに分割でき、f(P)が１個減る。よってそのような分割をf(P)-M回行えばよい。
  • 以下のコードではf(P)-M回Union-findによる巡回列探索を行っているが、何とか間に合う。

int N,M;
int P[3005],R[3005];
int num[3005];
int vis[3005];
class UF {
	public:
	static const int ufmax=5002;
	int ufpar[ufmax],ufrank[ufmax];
	UF() { init();}
	void init(){int i; FOR(i,ufmax) { ufpar[i]=i; ufrank[i]=0; } }
	int find(int x) {	return (ufpar[x]==x)?(x):(ufpar[x] = find(ufpar[x]));}
	int operator[](int x) {return find(x);}
	void unite(int x,int y) {
		x = find(x); y = find(y);
		if(x==y) return;
		if(ufrank[x]<ufrank[y]) ufpar[x]=y;
		else {ufpar[y]=x; if(ufrank[x]==ufrank[y]) ufrank[x]++;}
	}
};

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	FOR(i,N) cin>>P[i],P[i]--,R[P[i]]=i;
	cin>>M;
	
	UF uf;
	int cs=0;
	FOR(i,N) uf.unite(i,P[i]);
	FOR(i,N) num[uf[i]]++, cs+=(i!=uf[i]);
	
	int dif=abs(cs-M);
	
	_P("%d\n",dif);
	if(cs<M) {
		FOR(x,N) for(y=x+1;y<N;y++) if(dif && uf[x]!=uf[y]) {
			_P("%d %d ",x+1,y+1);
			dif--;
			uf.unite(x,y);
		}
		_P("\n");
	}
	else if(cs>M) {
		while(dif) {
			UF uf2;
			FOR(i,N) uf2.unite(i,P[i]);
			FOR(x,N) if(P[x]!=x) for(y=x+1;y<N;y++) if(uf2[x]==uf2[y]) {
				_P("%d %d ",x+1,y+1);
				swap(P[x],P[y]);
				dif--;
				goto out;
			}
			out:
			;
		}
		_P("\n");
	}
	
}

まとめ

f(P)を増やすのと減らすので微妙にアプローチが変わるのが面白い。