問題

問題概要

$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,*)$ をまとめて計算することを考えてみる。そのために、 $l$ を $n$ から $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;
}

裏紙

ほぼ競プロ、たまに日記

CF 749 E - Inversions After Shuffle

問題

問題概要

アイデア

実装(C++)