AtCoder ARC #110 (鹿島建設プログラミングコンテスト2020) : F - Esoswap

Eよりは簡単な気がする。
https://atcoder.jp/contests/arc110/tasks/arc110_f

問題

0～(N-1)のPermutationである数列Pが与えられる。
添え字iを選択すると、P[i]とP[(i+P[i])%N]がswapするものとする。
Pを昇順にせよ。

解法

今1～Kが昇順に並んでいるとする。
その時、1～Kのある位置を順に選択すると、1～Kが一つ右にシフトする。
これを繰り返しKの右に(K+1)が来るようにする。

これをずっと行えば1～(N-1)が順に並び、結果的に0～(N-1)が順に並ぶことになる。
ただこれだと0が先頭に来ていない可能性があるが、この時は1がある位置を連打すれば徐々に全体がシフトされていくのでいずれ0が先頭に来る。

int N;
int A[101],P[101];
vector<int> R;

void go(int x) {
	R.push_back(x);
	int y=(x+A[x])%N;
	swap(A[x],A[y]);
	P[A[x]]=x;
	P[A[y]]=y;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		P[A[i]]=i;
	}
	
	for(i=1;i<N-1;i++) {
		while((P[i]+1)%N!=P[i+1]) {
			for(j=1;j<=i;j++) go(P[j]);
		}
	}
	
	
	while(1) {
		FOR(i,N) if(A[i]!=i) break;
		if(i==N) break;
		go(P[1]);
	}
	
	FOR(i,N) assert(A[i]==i);
	
	cout<<R.size()<<endl;
	FORR(c,R) cout<<c<<endl;
	
}

まとめ

うーん、これ思い浮かばず…。