Codeforces #692 Div1 D. The Thorny Path

この解法は以前も見たことあるかも。
https://codeforces.com/contest/1464/problem/D

問題

1～NのPermutation Pを考える。
Pのスコアを、以下のように定める。
N頂点のグラフで、i→P[i]に辺を張る。
スコアはこのグラフにおける連結成分の頂点数の積とする。

Pの要素をいくつかswapし、上記積を最大化したい。
その最大値と、swap回数の最小値を求めよ。

解法

まず積の最大化だが、基本的に3*3*3*3...とするのが最適。
ただし残り4頂点の場合は3*1に分解するよりは2*2に分解した方がよい。

次にswap回数を求める。
これも既存の連結成分から極力長さ3の閉路を切り出し、余ったものをくっ付けて長さ3のものを作っていこう。

int T;
int N;
int P[1010100];
int did[1010101];
const ll mo=1000000007;

int hoge(vector<int> V) {
	int ret=0;
	int C[3]={};
	int can4=0;
	FORR(v,V) {
		ret+=(v-1)/3;
		C[v%3]++;
		if(v%3==1&&v>=4) can4=1;
	}
	
	if(N%3==2) {
		if(C[2]) C[2]--;
		else ret++, C[1]-=2;
	}
	else if(N%3==1) {
		//2*2
		if(C[2]>=C[1]+2) { // 2 2
			C[2]-=2;
		}
		else if(can4) { // 4
			ret--;
			C[1]--;
		}
		else if(C[2]>=1) { // 2, 1+1
			C[2]--;
			C[1]-=2;
			ret++;
		}
		else if(C[1]>=4) { // 1+1 1+1
			C[1]-=4;
			ret+=2;
		}
		else { // 3+1
			C[1]--;
			ret++;
		}
	}
	// 1+2
	int m=min(C[1],C[2]);
	C[1]-=m;
	C[2]-=m;
	ret+=m;
	
	ret+=2*C[1]/3; // 1+1+1 for 2swap
	ret+=C[2]; // 2+2+2 for 3wrap
	return ret;
	
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) {
			cin>>P[i];
			P[i]--;
			did[i]=0;
		}
		vector<int> V;
		FOR(i,N) if(did[i]==0) {
			int cnt=0;
			x=i;
			while(did[x]==0) cnt++, did[x]=1, x=P[x];
			V.push_back(cnt);
		}
		
		ll pat=1;
		x=N;
		while(x>=5) {
			pat=pat*3%mo;
			x-=3;
		}
		pat=pat*x%mo;
		
		cout<<pat<<" "<<hoge(V)<<endl;
		
		
	}
}

まとめ

解法そのものより、コーナーケースをつぶしていくのが手間な問題。