yukicoder : No.100 直列あみだくじ

面白かったです。
http://yukicoder.me/problems/178

問題

あみだくじにおいて、各出発点xに対応する到達点A[x]が与えられる。
同じ形状のあみだくじを縦に２つ繰り返した形状で、与えられた対応関係を実現するものは存在するか。

解法

あみだくじ１回分辿るとx→C[x]に到達するとする。
C[C[x]]==A[x]となるCが存在するか判定したい。

x==A[x]なxについては、C[x]==xとしてしまえばよい。

x!=A[x]の場合、C[x]の値を総当たりする。
その際、C[C[x]]=A[x]でなければならないので、C[C[x]]の値が定まる。
そこで、y=C[x]とするとC[y]の値が求まることになる。
同様に、続けてC[C[y]]=A[y]よりz=C[y]とするとC[z]が求まる…とDFSでC[x],C[y],C[z]…を順次求めていき、矛盾がないことを調べればよい。

…と思ったら、writer解によると「偶数サイズのループがそれぞれ偶数含まれる」判定だけでよいのか。

int N;
int A[100],C[100];
ll used;

bool dfs(int cur) {
	int ne=C[cur];
	
	if(C[ne]!=-1) return C[ne]==A[cur];
	C[ne]=A[cur];
	bool ret=dfs(ne);
	C[ne]=-1;
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	FOR(i,N) cin>>A[i], A[i]--;
	MINUS(C);
	FOR(i,N) if(A[i]==i) C[i]=i, used |= 1LL<<i;
	
	FOR(i,N) if(C[i]==-1) {
		FOR(j,N) if((used & (1LL<<j))==0) {
			if(C[j]!=-1 && C[j]!=A[i]) continue;
			y=C[j];
			C[i]=j;
			C[j]=A[i];
			if(dfs(j)) break;
			C[i]=-1;
			C[j]=y;
		}
		if(C[i]==-1) return _P("No\n");
	}
	return _P("Yes\n");
}

まとめ

最初転置行列の平方根を求めるのかと思ってしまった。