kmjp's blog

競技プログラミング参加記です

Codeforces #1030 : Div2 F. Shifts and Swaps

これで木構造が出てくるのか…。
https://codeforces.com/contest/2118/problem/F

問題

N要素の整数列A,Bが与えられる。いずれも、1~Mの整数を1個以上含む。
Aに対し以下の処理を任意の回数行える時、A=Bにできるか判定せよ。

  • Aをローテートする
  • Aのうち隣接する要素について、差が2以上の場合swapする

解法

両数列を木で表現し、それらが同型になりうるかで判断する。
A[j]=A[i]となる最小のj>iを考える。A[k]=A[i]-1かつi<k<jとなるとき点iと点kの間に辺を張ろう。
そうしてできる森のハッシュ値を取り、木単位でローテートして一致するかを判定する。

int T,N,M;
int A[505050],B[505050];
vector<int> E[1505050];

int X[505050],Y[505050];

ll tree_normalize(vector<ll> T) {
	static ll momo[2]={1000000007,1000000021};
	static ll sa=0,sb=0;
	
	if(sa==0) {
		srand(time(NULL));sa=rand()%(123456789);sb=rand()%(123456789);
	}
	
	ll a=sa,b=sb;
	int add=1;
	FORR(r,T) {
		ll h=r>>32, l=r-(h<<32);
		(a*=h+add++)%=momo[0];
		(b*=l+add++)%=momo[1];
	}
	return (a<<32)+b;
}

ll dfs(int cur,int pre) {
	vector<ll> H;
	FORR(e,E[cur]) if(e!=pre) H.push_back(dfs(e,cur));
	return tree_normalize(H);
}

using VT = vector<ll>;

vector<int> Zalgo(VT s) {
	vector<int> v(1,s.size());
	for(int i=1,l=-1,r=-1;i<s.size();i++) {
		if(i<=r && v[i-l]<r-i+1) v.push_back(v[i-l]);
		else {
			l=i; r=(i>r)?i:(r+1);
			while(r<s.size() && s[r-i]==s[r]) r++;
			v.push_back((r--)-l);
		}
	}
	v.push_back(0);
	return v;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,2*N+2) {
			E[i].clear();
		}
			
		FOR(i,N) {
			cin>>A[i];
			A[i]--;
		}
		FOR(i,M+2) {
			X[i]=Y[i]=1<<20;
		}
		FOR(i,N) {
			cin>>B[i];
			B[i]--;
		}
		FOR(i,2*N) {
			X[A[i%N]]=i;
			Y[B[i%N]]=i;
			if(X[A[i%N]+1]<N) E[X[A[i%N]+1]].push_back(i%N);
			if(Y[B[i%N]+1]<N) E[Y[B[i%N]+1]+N].push_back(i%N+N);
		}
		
		vector<ll> P,Q;
		FOR(i,N) {
			if(A[i]==M-1) P.push_back(dfs(i,i));
			if(B[i]==M-1) Q.push_back(dfs(i+N,i+N));
		}
		
		if(P.size()!=Q.size()) {
			cout<<"NO"<<endl;
			continue;
		}
		
		vector<ll> Z;
		Z=Q;
		Z.push_back(-1);
		FORR(p,P) Z.push_back(p);
		FORR(p,P) Z.push_back(p);
		auto V=Zalgo(Z);
		
		FOR(i,P.size()) if(V[P.size()+1+i]>=P.size()) break;
		
		
		if(i==P.size()) {
			cout<<"NO"<<endl;
		}
		else {
			cout<<"YES"<<endl;
		}
	}
}

まとめ

木構造になるの思いつかないな…。