UnKoder #01 : Colorful Cards

yukicoderの同作者の問題で似たのを見た。
https://www.hackerrank.com/contests/unkoder-01/challenges/colorful-cards-1

問題

N毎のカードがある。
各カードの表面の色はA[i]で、裏面はB[i]である。
表面A[0]～A[N-1]は互いに異なる色で、裏面B[0]～B[N-1]も互いに異なる色である。
また、使われている色は0～(N-1)のN色である。

ここで、任意のK枚以下のカードを裏返す、ということを繰り返す。
同じ色が複数表を向く瞬間が無いように、全カード裏面が表を向くようにできるか。

解法

まず入力を並べ替えて、(0-indexで)i番目のカードは表がi番の色、裏がC[i]番の色となるようにしておく。

ここでP枚裏返す場合、残りの(N-P)枚の表を向いた面の色は変わらないことになる。
そのため、裏返す前のP枚の表面の色の集合と、裏返した後のP枚の表面の色の集合は一致していなければならない。

上記条件を満たす裏返し方として、i番を裏返すと色C[i]番が表を向くので、同時にC[i]番を裏返す必要があり、するとC[C[i]]番の色が表を向くので、同時にC[C[i]]番を裏返す…という手段が考えられる。
この裏返し方がK枚以下で済むには、各iについてi→C[i]→C[C[i]]→C[C[C[i]]]→…という数列の周期がK以下であれば良い。
よって上記数列の周期を求めれば判断できる。

int N,K;
pair<int,int> P[60];
int X[60];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) cin>>P[i].first, P[i].first--;
	FOR(i,N) cin>>P[i].second, P[i].second--;
	FOR(i,N) X[P[i].first]=P[i].second;
	
	FOR(i,N) {
		x=1;
		y=X[i];
		while(y!=i) x++, y=X[y];
		if(x>K) return _P("No\n");
	}
	
	_P("Yes\n");
}

まとめ

これK枚ちょうどしかひっくり返せない場合、どう解けばいいんだろうな。