裏紙

ほぼ競プロ、たまに日記

ARC 043 C - 転倒距離

問題

C: 転倒距離 - AtCoder Regular Contest 043 | AtCoder

問題概要

1からNまでの整数を並び替えたものをサイズNの順列として,サイズNの順列XYに対して,その2つで順序が入れ替わっている数字の組の個数をXYの転倒距離とするときに,XともYとも転倒距離の等しいサイズNが存在するかを判定し,存在するならそのうちの1つを答えよ.

  • 1 \le N \le 10^5

イデア

まず,XYの転倒距離をT(X,Y)と表すことにしよう.すると,T(X,Z) = T(Y,Z)なるZが存在するならZが答えになる.またこのようなZが存在する時,T(X,Y)は偶数になる.まずこれを示す.

サイズNの順列について,数字の組は \frac{n(n-1)}{2}個あるが,その各組について,次の4通りに分かれる:

  • XZでは違う並び,YZでも違う並び
  • XZでは違う並び,YZでは同じ並び
  • XZでは同じ並び,YZでは違う並び
  • XZでは同じ並び,YZでも同じ並び

この4通りについて,各組の個数をそれぞれ x_1 , x_2 , x_3 , x_4とすると,T(X,Z) = x_1 + x_2 , T(Y,Z) = x_1 + x_3 となる.そして,T(X,Y) = x_2 + x_3 であるから,T(X,Z)T(T,Z)を使って表すと,T(X,Y) = T(X,Z) + T(Y,Z) - 2*x_1 となる.更にいまT(X,Z) = T(Y,Z)であるから,T(X,Y)は偶数になる.

対偶を取ればT(X,Y)が奇数ならばT(X,Z) = T(Y,Z)なるZが存在しないとなる.以下,解が存在する場合について考えていくことにする.

まず,数字の大小は影響しないので,Xの方を昇順になるように数字を変換する.すると,Xはソートされた形になり,Yとの転倒距離の見通しが立てやすい.具体的には,Yの各要素について,それよりも左側にあるその要素より大きい物を数え上げれば転倒距離を計算できる.そして,これは転倒数として知られており,バブルソートにおける交換回数と一致することが知られている.

すると,予め転倒数を計算してその転倒数をaとすると \frac{a}{2}回交換されるまでバブルソートをすることでO(N^2)の解答が得られるが,これでは速度が足りない.

バブルソートを逐一やっているのでは間に合わないので,ある程度まとめることを考える.バブルソートの過程を見ると,各過程において,その数字がしかるべき位置までにスワップが発生する回数は最初の数列の状態でその数よりも左にある数でその数よりも大きい数の個数に一致することに気づく.

それを逐次更新しながら,個数を高速に数え上げるためにはBITやSegtreeが有効である.よって,この部分の実装の流れとしては,まずSegtreeを使いながら転倒数を逐次更新していき,まず全体の転倒数aを求め,そこから \frac{a}{2}を越えないように1つずつバブルソートを進めていって越えそうになる直前でバブルソートに切り替えて \frac{a}{2}に到達させればよいということになる.

また,転倒数が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;
}