AtCoder ABC #371 : G - Lexicographically Smallest Permutation

575ptの割に手間取った…。
https://atcoder.jp/contests/abc371/tasks/abc371_g

問題

1～Nの順列である数列P,Aが与えられる。
Aの全要素を、A[i] = A[P[i]]で一斉に置き換える操作を何度でも行える時、Aを辞書順最小化せよ。

解法

Aの先頭から見て、未確定なものから決めて行く。
Pがいくつかの巡回置換からなることを考える。
A[0]はまず置換可能な値の最小値を取ればよい。
次に、A[1]が未確定なら、また置換可能な値の最小値を取ればよい…のだが。

もしA[0]がX要素の巡回置換に対しY回置換した場合、A[1]を決めるのに行える置換回数は、Xで割った余りがYとなるような値に制限される。
この手順を愚直に行うと、それまで行った置換に対し、CRTで行える置換回数の条件を求めればよいのだが、巡回置換の要素数のLCMがとても大きくなるのが問題。

そこで、以下のようにした。
もし「X要素の巡回置換に対しY回置換した」ならば、Xの約数Zに対しては、(Y%Z)回の置換が許容されるといえる。
この値をZごとに覚えておき、今W要素の巡回置換を考えるときはWの約数Z'に対し、上記条件に反しないかチェックした。

int N;
int P[202020];
int A[202020];
int B[202020];
int vis[202020];
int G[202020];

vector<int> D[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=200000;i++) {
		for(j=i;j<=200000;j+=i) D[j].push_back(i);
	}
	
	MINUS(G);
	
	cin>>N;
	FOR(i,N) {
		cin>>P[i];
		P[i]--;
	}
	FOR(i,N) cin>>A[i];
	set<int> S;
	FOR(i,N) if(vis[i]==0) {
		vector<int> V={i};
		vis[i]=1;
		while(P[V.back()]!=i) {
			V.push_back(P[V.back()]);
			vis[V.back()]=1;
		}
		
		set<int> cand;
		FOR(j,V.size()) cand.insert(j);
		
		int b=V.size();
		FORR(s,D[b]) if(G[s]!=-1) {
			set<int> cand2;
			FORR(a,cand) if(a%s==G[s]) cand2.insert(a);
			cand=cand2;
		}
		x=-1;
		FORR(c,cand) if(x==-1||A[V[c]]<A[V[x]]) x=c;
		FOR(j,V.size()) B[V[j]]=A[V[(j+x)%V.size()]];
		
		FORR(s,D[b]) G[s]=x%s;
	}
	
	FOR(i,N) cout<<B[i]<<" ";
	cout<<endl;
	
	
}

まとめ

最初LCMが大きくなりそうで頭抱えた。
この解法、もっと時間かかるかと思ったけど意外と早かったな。