AtCoder ARC #124 : D - Yet Another Sorting Problem

なんとかレート微増したけども。
https://atcoder.jp/contests/arc124/tasks/arc124_d

問題

1～(N+M)のPermutation Pが与えられる。
Pのうち、前半N要素のうち1つと、後半M要素のうち1つを選択し、swapする処理を行えるとする。
Pを昇順にするのにかかる最小要素数を求めよ。

解法

Pから対応するfunctional graphを考えてみる。
各連結成分において、前半N要素と後半M要素のうち、両方を1個以上含む場合、閉路長が2になるまでは、1処理毎に1要素だけ正しい位置に移動させ、かつ前半N要素と後半M要素に含まれる要素が1個以上残すようにできる。
よって、閉路長がLなら、(L-1)処理で正しい位置に配置できる。

残り、前半N要素内だけで構成される長さ2以上の閉路と、後半M要素内だけで構成される長さ2以上の閉路を考える。
前半N要素内のものを考えると、どうしても一度後半の要素を巻き込まないとswapできないので、必要処理数は(L+1)になる。
ただし、前半N要素内だけの閉路と、後半M要素内だけの閉路があれば、それらをペアにすると、処理数はその総長で抑えられる。

int N,M;
int P[202020];
int vis[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N+M) {
		cin>>P[i];
		P[i]--;
	}
	int ret=0;
	int AO=0,BO=0;
	FOR(i,N+M) if(vis[i]==0) {
		int A=0,B=0;
		int cur=i;
		if(cur<N) A++;
		else B++;
		vis[i]=1;
		while(P[cur]!=i) {
			cur=P[cur];
			if(cur<N) A++;
			else B++;
			vis[cur]=1;
		}
		if(A+B>1) {
			if(A==0||B==0) {
				ret+=A+B;
				if(A>0) AO++;
				if(B>0) BO++;
			}
			else ret+=A+B-1;
		}
	}
	
	ret+=abs(AO-BO);
	
	cout<<ret<<endl;
}

まとめ

本番細かいところでミスを重ねてしまい残念。