これで木構造が出てくるのか…。
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; } } }
まとめ
木構造になるの思いつかないな…。