しんどかったです…。
https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_j
問題
N(2の累乗)要素からなる2つの数列S[0],Tが与えられる。
i回目の処理では、以下の手順でS[i]を生成できる。
- 2つのi未満のindex x,yを選択する。また、整数fを定める。
- S[i][j] = S[x][j]またはS[y][j-f]のいずれを取るか、j毎に選択できる。
500回以内にS[i]=Tを構築する手順を答えよ。
解法
Editorialの記述が少ないので、Editorial見て解法にたどり着くのは結構大変。
Writer解を見るに、以下の手順を踏んでいる。
まず、Tに現れる要素が全てS[0]のどこかに現れていることを確認しよう。
SとTの要素が並べ替えだけで一致するとは限らないので、一部要素は登場回数を増減させる必要がある。
並べ替えと増減を一気に行うのは難しいので、別々に行うことにしよう。
仮にS[0]="1 6 4 8 7 2 5 3"、T="1 3 3 7 3 1 3 3"とする。この場合、中に1が2個、3が5個、7が1個含まれている。
以下のようにまずS[0]のうち必要な要素を並べ替え、その後Tの登場回数分だけ増幅させる。
そして再度並べ替えて所定の位置に合わせよう。
S[0]= 1 6 4 8 7 2 5 3 ↓並べ替え S[a] = 1 * 3 * * * * 7 ↓ 複製 S[b] = 1 1 3 3 3 3 3 7 ↓並べ替え T = 1 3 3 7 3 1 3 3
複製はO(logN)回の処理で行える。
あと2回の並べ替えは同じロジックで対応できる。
(国内のみのコンテストのため解答例もないが、Write解含め多くの例で似た処理を2回やっているのはそのため)
並べ替えはO(log^2 N)回の処理で対応できる。
1つ目のlogだが、初回のループでN個中前半に来るべきN/2個を前半、後半に来るべきN/2個を後半に持っていく。
2回目のループでは、それぞれのN/2個内で、前半に来るべきN/4個を前半、後半に来るべきN/4個を後半に持っていく…
という要領を繰り返せばよい。
次に、個々のループで「N個中前半に来るべきN/2個を前半、後半に来るべきN/2個を後半に持っていく」ができればよい。
こちらもO(log N)回の処理で対応できる。
i回目のループでは、各要素の位置をmod 2^iで分類したとき、前半にくべきN/2個の数と後半にくべきN/2個の数が均等になるようにし、その際「前半にくべきN/2個」ができるだけ前に来るようにしよう。
そのためには、A[x]とA[x | (2^(i-1)]を比較する。
両者のうち片方が前半、片方が後半にあるようなケースがいくつかあったとする。(その数は必ず偶数である)
その場合、xの小さい順半分のケースでは、前半にくべきものを前半、残り半分では前半にくべきものを後半に持っていく。
そうすると、「前半にくべきN/2個の数と後半にくべきN/2個の数が均等になるようにし、その際「前半にくべきN/2個」ができるだけ前に来る」ようになる。
なお、要素のswapはf=(2^(i-1))とf=-(2^(i-1))の2手でできる。
ab ↓ (f = -1)でaを右にコピー aa ↓ (f = 1)で2手前のbを左にコピー ba
int N; int S[505][9090]; int T[9090]; int pos[9090]; vector<int> D[9090]; vector<pair<ll,string>> event; void add(int x,int y,int f,string T) { ll key=1LL*x*1000000000LL+1LL*y*100000+(f+10000); event.push_back({key,T}); int cur=event.size(); assert(x>=0 && y>=0 && x<cur && y<cur && T.size()==N); int i; FOR(i,N) { if(T[i]=='x') S[cur][i]=S[x][i]; else { assert(i-f>=0 && i-f<N); S[cur][i]=S[y][i-f]; } } } void hoge(vector<int> dest) { int i; for(int step=N/2;step>=1;step/=2) { vector<int> NS(N); FOR(i,N) NS[i]=(dest[i]&step)!=0; for(int sh=1;sh<=step;sh*=2) { string C[2]; C[0]=C[1]=string(N,'x'); for(int cur=0;cur<N;cur+=step*2) { for(int dif=0;dif<sh;dif++) { int notsame=0; for(i=cur+dif;i<cur+(step*2);i+=sh*2) { if(NS[i]!=NS[i^sh]) notsame++; } notsame/=2; for(i=cur+dif;i<cur+(step*2);i+=sh*2) { if(NS[i]==0 && NS[i^sh]==1) { if(sh!=step && notsame<=0) { swap(NS[i],NS[i^sh]); swap(dest[i],dest[i^sh]); C[0][i^sh]='y'; C[1][i]='y'; } notsame--; } else if(NS[i]==1 && NS[i^sh]==0) { if(sh==step || notsame>0) { swap(NS[i],NS[i^sh]); swap(dest[i],dest[i^sh]); C[0][i^sh]='y'; C[1][i]='y'; notsame--; } } } } } int cur=event.size(); add(cur,cur,sh,C[0]); add(cur+1,cur,-sh,C[1]); } } } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; MINUS(pos); FOR(i,N) { cin>>S[0][i]; S[0][i]--; pos[S[0][i]]=i; } FOR(i,N) { cin>>T[i]; T[i]--; if(pos[T[i]]==-1) return _P("-1\n"); D[T[i]].push_back(i); } vector<int> dest(N,-1); set<int> unused; FOR(i,N) unused.insert(i); int ok=0; FOR(i,N) { if(D[i].size()>0) { unused.erase(ok); dest[pos[i]]=ok; ok+=D[i].size(); } } FOR(i,N) if(dest[i]==-1) { dest[i]=*unused.begin(); S[0][i]=-1; unused.erase(unused.begin()); } hoge(dest); vector<int> from(N,0); int pre=0; FOR(i,N) { if(S[event.size()][i]>=0) pre=i; else from[i]=i-pre; } for(int step=1;step<=N/2;step*=2) { string T=string(N,'x'); FOR(i,N) if((from[i]&step)&&step*2>from[i]) T[i]='y'; add(event.size(),event.size(),step,T); } FOR(i,N) { dest[i]=D[S[event.size()][i]].back(); D[S[event.size()][i]].pop_back(); } hoge(dest); FOR(i,N) assert(S[event.size()][i]==T[i]); cout<<event.size()<<endl; FORR(e,event) { ll x=e.first/1000000000LL; ll y=e.first/100000LL%10000; ll f=e.first%100000-10000; cout<<x<<" "<<y<<" "<<f<<" "<<e.second<<endl; } }
まとめ
もう少しEditorial書いて欲しいです…理解するのに苦労した。