AtCoder ARC #154 : C - Roller

開始10分でC問題まで解けたは良いが、そこで失速…。
https://atcoder.jp/contests/arc154/tasks/arc154_c

問題

N要素の整数列A,Bが与えられる。
A[i]をA[i+1]で置き換える(ただし、A[N-1]についてはA[0]で置き換える)ことを繰り返し、AとBを一致させられるか。

解法

初期状態でA=Bなら一致可能。
それ以外の場合、Aを最低1回は操作することから、Bのうち2要素同じ値が続く箇所がないといけない。
そのような箇所があった場合、A,Bをそれぞれ連続する同じ値を1つに圧縮した数列に置き換えて考える。

Aをrotateしたのち、部分列を取ってBと一致できるなら条件を満たす。
よってrotate回数を総当たりし、そのつどAの部分列でBと一致させられるか判定しよう。

int T;
int N;
int A[5555],B[5555];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) cin>>A[i];
		FOR(i,N) cin>>B[i];
		
		FOR(i,N) if(A[i]!=B[i]) break;
		if(i==N) {
			cout<<"Yes"<<endl;
			continue;
		}
		
		FOR(i,N) if(B[i]==B[(i+1)%N]) break;
		if(i==N) {
			cout<<"No"<<endl;
			continue;
		}
		
		vector<int> X,Y;
		FOR(i,N) {
			if(X.empty()||X.back()!=A[i]) X.push_back(A[i]);
			if(Y.empty()||Y.back()!=B[i]) Y.push_back(B[i]);
		}
		if(X.size()!=1&&X[0]==X.back()) X.pop_back();
		if(Y.size()!=1&&Y[0]==Y.back()) Y.pop_back();
		int ok=0;
		FOR(i,N) {
			rotate(X.begin(),X.begin()+1,X.end());
			int cur=0;
			FORR(x,X) if(cur<Y.size()&&Y[cur]==x) cur++;
			if(cur==Y.size()) ok=1;
		}
		
		if(ok) {
			cout<<"Yes"<<endl;
		}
		else {
			cout<<"No"<<endl;
		}
		
		
	}
}

まとめ

これはすんなり思いついてよかったね。