AtCoder ABC #302 (トヨタ自動車プログラミングコンテスト2023#2) : G - Sort from 1 to 4

こっちはすんなりだった。
https://atcoder.jp/contests/abc302/tasks/abc302_g

問題

各要素1～4で構成される数列Aが与えられる。
任意の2要素のswapを繰り返し、Aを単調増加にしたい。
最小何回swapが必要か。

解法

1～4のラベルを持つ4頂点の有向グラフを考える。
最初A[i]=xだが、単調増加にした暁にはA[i]=yでなければならないようなiがあった場合、x→yに有向辺を張ろう。

このグラフにおいて、長さLの閉路があった場合、(L-1)回のswapを繰り返すとL要素を正しい位置に配置できる。
つまり、短い閉路を見つければそれだけswap回数を減らせることになる。
長さ2・3・4の順で閉路を探し取り除いていこう。

要素の種類がMの時、以下のコードはO(NlogN+M!)である。

int N;
int A[202020],B[202020];
int dp[4][4];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		B[i]=--A[i];
	}
	sort(B,B+N);
	FOR(i,N) if(A[i]!=B[i]) dp[A[i]][B[i]]++;
	int num=0;
	vector<int> V={0,1,2,3};
	for(i=2;i<=4;i++) {
		do {
			x=1<<30;
			FOR(j,i) {
				x=min(x,dp[V[j]][V[(j+1)%i]]);
			}
			num+=(i-1)*x;
			FOR(j,i) {
				dp[V[j]][V[(j+1)%i]]-=x;
			}
			
		} while(next_permutation(ALL(V)));
	}
	
	cout<<num<<endl;
	
	
}

まとめ

Mがもうちょい大きくても困らないんだけど、想定解法じゃないんかな。