読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

CF 749 E - Inversions After Shuffle

問題

Problem - E - Codeforces

問題概要

1からnまでの数を並べた長さnの順列がある。1回だけ以下の操作を行う:

全ての区間\frac{n(n+1)}{2}個のうち、区間(lからr)をランダムに選ぶ。そして、その区間の長さをk(=r-l+1)とし、その区間に対して、シャッフルを行う(つまり、k!通りの並び替え方のうち、ランダムに1つ選ぶ)。

この操作の後にできあがる数列の反点数の期待値を求めよ。

  • 1 \le n \le 100000

イデア

以下、配列は問題に従って1-indexで考えることにする。

考えるべき区間の選び方は \frac{n(n+1)}{2}個あるわけなので、これが分母になってくるとして考えていくことにする。

考察にあたり、もう一つ重要なことはただ単に順列の全体をシャッフルした時の反転数は\frac{n(n-1)}{4}ということである。これは、1つの配列に対して、それをreverseしたような配列を考えてみると、その2つの配列の反点数の和が\frac{n(n-1)}{2}になっており、そのようなreverseしたもののpairが全ての順列に対して見つかるので、それを2で割ったものということである。

上記の考えから、この問題において求めるべき値は与えられる順列a区間 [ l, r ]の反点数をinv(l,r)とおくと、次のようになる:

 \displaystyle \sum_{ 1 \le l \le r \le n} \frac{ inv(1,n) - inv(l,r) + \frac{(r-l+1)(r-l)}{4} }{ \frac{n(n+1)}{2} }

分子がなぜこのような形になるのか、区間 [ l, r ]をシャッフルした後に、その順列全体の反点数がどのように変化するかを考える。すると、2つのindexに対して、反点数に変化があるかどうかは、どちらかのindexがこのシャッフルの区間の外ならその順番が入れ替わることはないので反点数は変化しないわけである。つまり、反点数が変化しうるのはこの区間内についてのみ注目すればいいということになる。そして、前述の通り長さnの順列をシャッフルした時の反点数の期待値は\frac{n(n-1)}{4}であるから、その元の反点数を引いてその期待値を足しているという式の形になっている。

さて、ただこれを愚直に計算するのでは間に合わない。分母はconstなので、分子をどうするか考えてみると、全体の反点数についてはBITなどをつかうことによってO(nlogn)で計算が可能であり、この分数についても、r-lに着目すればn種類の値がそれぞれ何回ずつ現れるのかが簡単にわかるのでO(n)で計算できる。

そして残るは \sum_{ 1 \le l \le r \le n} inv(l,r)の計算である。以下で、これについて考える。

いま、inv(l,*)をまとめて計算することを考えてみる。そのために、lnから1の方向に動かしながら考えていく。そして、配列bを考えて、b_i = \sum_{i \le j \le n} inv(i,j)とする。

さて、このb_iの値について計算したいが、この値はb_{i+1}を使って表すことが出来る。それは区間 [i , j ]を [i , i ]と [i+1 , j ]に分けて考えることが出来るからである。

そして、いまは始点を固定しているので、この区間に対して例えばn番目の値は1つの区間( [i , n ])に入り得る。一方で、n-1番目の値に注目すると2つの区間( [i , n ]と [i , n-1 ])に入る。つまり、この2つの区間でこの反転がカウントされる。このようにiを固定したときにj番目の値は全部でn-j+1個の区間に入ってくることになる。

つまり、b_iを計算するときに、i \lt jなるjを考えて、その中でa_i \gt a_jとなっている位置のみに対してこの上記の反点数カウントをすればよいことになる。これは、まさにBITによって実現される。

(自分の用意してたBITにちょっとバグがあってそれに気づいて直すまでに時間かかった...このBITで何問か通してたはずなんだけど、見つかってよかった)

実装(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 BIT{
    // [1,n]
    int n; vector<ll> bit;
    // 初期化
    BIT(int _n){
        n = _n;
        bit = vector<ll>(n+1,0);
    }
    // sum of [1,i]
    ll sum(int i){
        ll s = 0;
        while(i>0){
            s += bit[i];
            i -= i & -i;
        }
        return s;
    }
    // add x in i-th element
    void add(int i, ll x){
        while(i<=n){
            bit[i] += x;
            i += i & -i;
        }
    }
};

ll invcount(int n, const vector<int>& a)
{
    ll ret=0;
    BIT b(n);
    for(int i=n; i>=1; --i)
    {
        ret+=b.sum(a[i]);
        b.add(a[i],1);
    }
    return ret;
}

int main()
{
    int n;
    scanf(" %d", &n);
    vector<int> a(n+1);
    for(int i=1; i<=n; ++i) scanf(" %d", &a[i]);

    // 全体の反点数の計算
    double ans = invcount(n,a)*0.5*n*(n+1);

    // 区間の長さがiの部分列の個数はn-i+1なのでそれを利用してシャッフル時の期待値を計算
    for(int i=1; i<=n; ++i) ans+=0.25*i*(i-1) * (n-i+1);

    // inv(l,r)の和を計算
    BIT bit(n);
    vector<ll> b(n+1,0);
    bit.add(a[n],1);
    for(int i=n-1; i>=1; --i)
    {
        b[i] = b[i+1]+bit.sum(a[i]);
        bit.add(a[i],n-i+1);
    }
    for(int i=1; i<=n; ++i) ans-=b[i];

    ans /= 0.5*n*(n+1);
    printf("%.12f\n", ans);
    return 0;
}