CF 749 E - Inversions After Shuffle
問題
問題概要
からまでの数を並べた長さの順列がある。1回だけ以下の操作を行う:
全ての区間個のうち、区間(から)をランダムに選ぶ。そして、その区間の長さをとし、その区間に対して、シャッフルを行う(つまり、通りの並び替え方のうち、ランダムに1つ選ぶ)。
この操作の後にできあがる数列の反点数の期待値を求めよ。
アイデア
以下、配列は問題に従って1-indexで考えることにする。
考えるべき区間の選び方は個あるわけなので、これが分母になってくるとして考えていくことにする。
考察にあたり、もう一つ重要なことはただ単に順列の全体をシャッフルした時の反転数はということである。これは、1つの配列に対して、それをreverseしたような配列を考えてみると、その2つの配列の反点数の和がになっており、そのようなreverseしたもののpairが全ての順列に対して見つかるので、それを2で割ったものということである。
上記の考えから、この問題において求めるべき値は与えられる順列の区間 ]の反点数をとおくと、次のようになる:
分子がなぜこのような形になるのか、区間 ]をシャッフルした後に、その順列全体の反点数がどのように変化するかを考える。すると、2つのindexに対して、反点数に変化があるかどうかは、どちらかのindexがこのシャッフルの区間の外ならその順番が入れ替わることはないので反点数は変化しないわけである。つまり、反点数が変化しうるのはこの区間内についてのみ注目すればいいということになる。そして、前述の通り長さの順列をシャッフルした時の反点数の期待値はであるから、その元の反点数を引いてその期待値を足しているという式の形になっている。
さて、ただこれを愚直に計算するのでは間に合わない。分母はなので、分子をどうするか考えてみると、全体の反点数についてはBITなどをつかうことによってで計算が可能であり、この分数についても、に着目すれば種類の値がそれぞれ何回ずつ現れるのかが簡単にわかるのでで計算できる。
そして残るはの計算である。以下で、これについて考える。
いま、をまとめて計算することを考えてみる。そのために、をからの方向に動かしながら考えていく。そして、配列を考えて、とする。
さて、このの値について計算したいが、この値はを使って表すことが出来る。それは区間 ]を ]と ]に分けて考えることが出来るからである。
そして、いまは始点を固定しているので、この区間に対して例えば番目の値は1つの区間( ])に入り得る。一方で、番目の値に注目すると2つの区間( ]と ])に入る。つまり、この2つの区間でこの反転がカウントされる。このようにを固定したときに番目の値は全部で個の区間に入ってくることになる。
つまり、を計算するときに、なるを考えて、その中でとなっている位置のみに対してこの上記の反点数カウントをすればよいことになる。これは、まさに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; }