kojingharangの日記

Codeforces #159 Div1 B - Playing with Permutations

12:44 |

• 置換 A を Ai in [1, N] (i in [1, N]), Ai≠Aj (i≠j, i, j in [1, N]) とする
• 置換 Q, S が与えられる。恒等置換 P に対して毎回 Q か Q^-1 を作用させる操作を K 回やる。
• 「0回目～K-1回目は P!=S だが、ちょうど K 回目で S に等しくなる」ということはありえるかどうか求める問題。
• N, K≦100

• * を作用させる演算子として、P * Q * Q^-1 == P と元に戻るのと、作用させる順番が関係ないので、K 回後の状態は P * Q^? とあらわせる
• なので、i＜K 回目はすべての場合で P!=S で i==K 回目で P==S となる場合があるときだけ YES とするようにしてみたけど sample があわない

• 途中で P==S になる場合があってもそこを通らずに K 回目で P==S となれば YES になるのか

• 結局 BFS をすることになった。
• 予め Same[j] = S == Q^j (j in [-K, K]) かどうかを計算しておいて、
• ノード i が Same じゃなければ i-1, i+1 をキューに追加
• K回目で Same なら YES

• ノード数は 2K+1 程度なので O(NK+K^2) くらい?

• ↓Accepted

ll N, K;
VI Q, S, P, W;
VI Same; // idx [-K K]  [0 2K]

int apply(int sign) {
	if(sign==1) {
		REP(i, N) W[i]=P[Q[i]-1];
	} else {
		REP(i, N) W[Q[i]-1]=P[i];
	}
	REP(i, N) P[i]=W[i];
	return 1;
}

int main() {
	//ios::sync_with_stdio(false);
	while(cin>>N>>K) {
		Q=VI(N);
		S=VI(N);
		P=VI(N);
		W=VI(N);
		Same=VI(2*K+1);
		REP(i, N) {
			cin>>Q[i];
		}
		REP(i, N) {
			cin>>S[i];
		}
		
		for(int sign=-1;sign<=1;sign+=2) {
			REP(i, N) P[i]=i+1;
			REP(i, K+1) {
				int same=1;
				REP(j, N) if(P[j]!=S[j]) same=0;
				//cout<<P<<endl;
				Same[i*sign + K] = same;
				apply(sign);
			}
		}
		//cout<<Same<<endl;
		//break;
		
		deque<int> q;
		q.PB(0);
		int OK=0;
		REP(loop, K+1) {
			deque<int> nq;
			VI vis(2*K+1);
			while(q.size()) {
				int idx = q.front();q.pop_front();
				//cout<<"loop "<<loop<<" pop "<<idx<<endl;
				if(loop==K && Same[idx+K]) {
					//cout<<" same at Kth"<<endl;
					OK=1;break;
				}
				if(loop<K && !Same[idx+K]) {
					//cout<<" not same"<<endl;
					if(!vis[idx-1+K]) {vis[idx-1+K]=1; nq.PB(idx-1); }
					if(!vis[idx+1+K]) {vis[idx+1+K]=1; nq.PB(idx+1); }
				}
			}
			//cout<<"NQ "<<nq<<endl;
			q = nq;
			if(q.size()==0) break;
		}
		
		
		cout<<(OK?"YES":"NO")<<endl;
		//break;
	}
	
	return 0;
}

ツイートする