Codeforces #1104 : E. Permutation Commutation

本番中に解けずじまい…。
https://codeforces.com/contest/2237/problem/E

問題

2つの順列A,Bが与えられる。
ただし、Bの一部要素は不定である。
Bの不定の箇所を埋め、A[B[i]]=B[A[i]]となるようにしたい。

条件を満たすBがれば、辞書順最小のものを答えよ。

解法

2つのFunctional Graphを考える、片方はi→A[i]、もう片方はi→B[i]のように辺を張る。
このグラフが条件を満たすには、

• 各iに対し、iが属する前者のグラフの閉路長と、後者のグラフの閉路長が同じ
• 前者の閉路と後者の閉路は、点の並び順が同じ

ここから、Bのうち確定している要素があればその値を含む閉路は一意に定まる。
あとは、Bの未確定の要素のうち、辞書順最小となるように先頭から埋めて行こう。

int T,N,A[202020],B[202020],vis[202020],used[202020];;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt,G[um];
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit(int num=um) {int i; FOR(i,num) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;
vector<int> cand[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>T;
	while(T--) {
		FOR(i,N) cand[i+1].clear();
		cin>>N;
		uf.reinit(N);
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
			uf(i,A[i]);
			vis[i]=used[i]=0;
		}
		FOR(i,N) {
			cin>>B[i];
			if(B[i]>0) B[i]--;
		}
		int fail=0;
		FOR(i,N) if(B[i]>=0&&vis[i]==0) {
			if(fail) break;
			if(uf.count(i)!=uf.count(B[i])) {
				fail=1;
				break;
			}
			x=A[i];
			y=B[i];
			k=uf.count(i);
			FOR(j,k) {
				x=A[x];
				y=A[y];
				if(B[x]==-1) B[x]=A[y];
				if(B[x]!=A[y]) {
					fail=1;
					break;
				}
				vis[x]=1;
				used[y]=1;
			}
		}
		
		FOR(i,N) if(used[i]==0) {
			cand[uf.count(i)].push_back(i);
			x=i;
			k=uf.count(i);
			FOR(j,k) {
				used[x]=1;
				x=A[x];
			}
		}
		FOR(i,N+1) reverse(ALL(cand[i]));
		
		FOR(i,N) if(B[i]==-1) {
			k=uf.count(i);
			if(cand[k].empty()) {
				fail=1;
				break;
			}
			x=cand[k].back();
			cand[k].pop_back();
			y=i;
			FOR(j,k) {
				B[y]=x;
				x=A[x];
				y=A[y];
			}
			
		}
		if(fail==0) {
			set<int> S;
			FOR(i,N) {
				S.insert(B[i]);
				if(A[B[i]]!=B[A[i]]) fail=1;
			}
			if(S.size()!=N) fail=1;
		}
		
		
		
		if(fail) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
			FOR(i,N) {
				cout<<B[i]+1<<" ";
			}
			cout<<endl;
		}
	}
}

まとめ

うーん、これは本番思いつかなかったな…。