Google Code Jam 2022 Round 3 : A. Revenge of GoroSort

GCJ R3で2問解けたの初めてかも。
https://codingcompetitions.withgoogle.com/codejam/round/00000000008779b4/0000000000b45189

問題

変則的なGoroSortを考える。
1～Nの番号が振られたN個の箱に、1個ずつボールが入っている。
ボールは、1～Nの番号を持つものが1ずつある。

この箱に対し、以下のようにボールの配置をシャッフルすることができる。

• 箱をグループ分けする
• その後、各グループ内でボールがシャッフルされる。

N=100であるとき、平均11.5手以下でボールと箱の番号を一致させるよう、グループ分けを答えよ。

解法

箱番号iと、そこに入っているボール番号jに対し、f(i)=jとなる関数fを考えると、箱とボールの関係はファンクショングラフで表すことができる。
ここで、各連結成分を同じグループに入れるようにしてみる。
そうすると、過去のGoroSortの知見より、1回の処理で各グループ平均1個はボールと箱が正しい関係に落ち着く。
また、多くのケースで1つの大きな閉路は、小さな複数の閉路に分割される。
そうすると、平均12手程度を達成できる。

ここからさらに手数を減らす場合、大きな閉路に関しては、全体で1グループでなく半分ずつ2グループにすることを考える。
そうすると、1回の処理で平均2個弱ボールと箱が正しい関係に落ち着くので、平均11手弱を達成できる。
以下のコードでは、長さ5以上の閉路を2グループに分割している。

int N,K;
int A[555];
int C[555];
int tstep;
void solve(int _loop) {
	int f,i,j,k,l,x,y;
	
	FOR(i,N) {
		cin>>A[i];
	}
	
	int step=0;
	while(1) {
		step++;
		int vis[100]={};
		int nc=1;
		FOR(i,N) if(vis[i]==0) {
			vector<int> V;
			int cur=i;
			while(vis[cur]==0) {
				vis[cur]=1;
				V.push_back(cur);
				cur=A[cur]-1;
			}
			if(V.size()<=4) {
				FORR(v,V) C[v]=nc;
				nc++;
			}
			else {
				FOR(j,V.size()) {
					if(j<V.size()/2) C[V[j]]=nc;
					else C[V[j]]=nc+1;
				}
				nc+=2;
			}
		}
		FOR(i,N) cout<<C[i]<<" ";
		cout<<endl;
		cin>>x;
		if(x==-1) exit(0);
		if(x==1) break;
		FOR(i,N) cin>>A[i];
		/*
		cerr<<step<<" ";
		FOR(i,N) cerr<<A[i]<<" ";
		cerr<<endl;
		*/
	}
	tstep+=step;
	cerr<<_loop<<" "<<step<<" "<<tstep<<endl;
	//_P("Case #%d:\n",_loop);
}

void init() {
	cin>>N>>K;
	
}

まとめ

なんかいろいろ試してたら11手を切れた。