ARC 043 C - 転倒距離
問題
C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder
問題概要
からまでの整数を並び替えたものをサイズの順列として,サイズの順列とに対して,その2つで順序が入れ替わっている数字の組の個数をとの転倒距離とするときに,ともとも転倒距離の等しいサイズが存在するかを判定し,存在するならそのうちの1つを答えよ.
アイデア
まず,との転倒距離をと表すことにしよう.すると,なるが存在するならが答えになる.またこのようなが存在する時,は偶数になる.まずこれを示す.
サイズの順列について,数字の組は個あるが,その各組について,次の4通りに分かれる:
- とでは違う並び,とでも違う並び
- とでは違う並び,とでは同じ並び
- とでは同じ並び,とでは違う並び
- とでは同じ並び,とでも同じ並び
この4通りについて,各組の個数をそれぞれとすると,となる.そして,であるから,とを使って表すと,となる.更にいまであるから,は偶数になる.
対偶を取ればが奇数ならばなるが存在しないとなる.以下,解が存在する場合について考えていくことにする.
まず,数字の大小は影響しないので,の方を昇順になるように数字を変換する.すると,はソートされた形になり,との転倒距離の見通しが立てやすい.具体的には,の各要素について,それよりも左側にあるその要素より大きい物を数え上げれば転倒距離を計算できる.そして,これは転倒数として知られており,バブルソートにおける交換回数と一致することが知られている.
すると,予め転倒数を計算してその転倒数をとすると回交換されるまでバブルソートをすることでの解答が得られるが,これでは速度が足りない.
バブルソートを逐一やっているのでは間に合わないので,ある程度まとめることを考える.バブルソートの過程を見ると,各過程において,その数字がしかるべき位置までにスワップが発生する回数は最初の数列の状態でその数よりも左にある数でその数よりも大きい数の個数に一致することに気づく.
それを逐次更新しながら,個数を高速に数え上げるためにはBITやSegtreeが有効である.よって,この部分の実装の流れとしては,まずSegtreeを使いながら転倒数を逐次更新していき,まず全体の転倒数を求め,そこからを越えないように1つずつバブルソートを進めていって越えそうになる直前でバブルソートに切り替えてに到達させればよいということになる.
また,転倒数がint型に収まらない可能性があるので注意(そのミスでで30分くらいバグをさがしつづけた)
実装(C++)
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i)) #define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr) #define all(x) (x).begin(),(x).end() #define pb push_back #define fi first #define se second struct SumSegTree{ long n; vector<ll> dat; //初期化 SumSegTree(long _n){ n=1; while(n<_n) n*=2; dat=vector<ll>(2*n-1,0); } //k番目(0-indexed)の値をaに変更 void update(long k, ll a){ k+=n-1; dat[k]=a; //更新 while(k>0){ k=(k-1)/2; dat[k]=dat[2*k+1]+dat[2*k+2]; } } //内部的に投げられるクエリ ll _query(long a, long b, long k, long l, long r){ if(r<=a || b<=l) return 0; if(a<=l && r<=b) return dat[k]; else{ ll vl=_query(a,b,2*k+1,l,(l+r)/2); ll vr=_query(a,b,2*k+2,(l+r)/2,r); return vl+vr; } } //[a,b)の和を求める ll query(long a, long b){ return _query(a,b,0,0,n); } }; int main() { int n; cin >>n; vector<int> x(n),y(n); rep(i,n) scanf(" %d", &x[i]); rep(i,n) scanf(" %d", &y[i]); //aが昇順になるように変換 vector<int> f(n+1); rep(i,n) f[x[i]]=i+1; rep(i,n) y[i]=f[y[i]]; SumSegTree s(n+2); vector<int> num(n+1); rep(i,n) { num[y[i]]=s.query(y[i]+1,n+1); s.update(y[i],1); } //転倒数 ll a=0; rep(i,n) a+=num[i+1]; //存在しない場合 if(a%2==1) { printf("-1\n"); return 0; } //存在する場合 ll ct=0; int now=0; while(now<n) { if(ct+num[now+1]>=a/2) break; ct+=num[now+1]; ++now; } //答えになる数列 vector<int> z; rep(i,now) z.pb(i+1); rep(i,n) if(y[i]>now) z.pb(y[i]); for(int i=n-1; i>now; --i) { if(z[i]<z[i-1]) { swap(z[i],z[i-1]); ++ct; } if(ct==a/2) break; } rep(i,n) { if(i) printf(" "); //元の数値に変換して表示 printf("%d", x[z[i]-1]); } printf("\n"); return 0; }