Kyoto University Programming Contest 2018 (KUPC2018) : E - 転倒数

かなり険しかった。
https://beta.atcoder.jp/contests/kupc2018/tasks/kupc2018_e

前提

Chokudai SpeedRun 001 : J - 転倒数
Chokudai SpeedRun 001 : K - 辞書順で何番目？
この2題によって、1つのBITで順列の転倒数と辞書順で何番目かを同時に求めることができるようになった。

問題

順列が与えられる。その順列より辞書順で小さいか等しいものの転倒数の総和を求めよ。

解法

公式解説
※以下ではすべて1-indexedだが、下記のソースコードでは順列が0-indexedであることに注意
まず、桁の順列の転倒数の総和を求める。これをとする。これは考察してDPをするか、実験してOEISすることで

とわかる。

辞書順で何番目？のときと同じように、番目で初めて順列よりも小さくなる順列たちの転倒数の総和を求めていく。
このとき、順列Aと等しい区間、、後で決める区間に分けて考え、これをゾーン1、ゾーン2、ゾーン3とする。

各に対して、
①ゾーン3の転倒数の総和
②ゾーン2とゾーン3をマージするための転倒数の総和
③ゾーン1とゾーン23をマージするための総和
をに足していけばよい。

ゾーン2の値として選ぶことができる要素の数をBITから計算する。

①ゾーン3をソートするための転倒数の総和は、ゾーン3の並べ方は自由なので、
]
である。
②ゾーン2とゾーン3のマージコストを考える。
ゾーン2の候補の中で番目に小さい値は、ゾーン2とゾーン3の中でも番目に小さい。
すなわち、回の転倒数が発生する。ゾーン3の並べ方は通りであるから、
これをすべてのゾーン2の候補について足し合わせると

である。
③ゾーン1とゾーン23のマージコストを考える
必要な転倒数はゾーン1のソートコストと、ゾーン1とゾーン23のマージコストである。
ゾーン1のソートコストは、BITから計算できた。
マージコストは当たり前だが、ゾーン1の各要素よりも小さいゾーン1にない(ゾーン23にある)要素の数の和である。

これはBITを使って更新していくことができる。
はまさにより小さいゾーン1にない要素の数であるからに加える。
ゾーン1により大きい数があった場合、がゾーン1としてソートされることでマージコストは減る。
からを引く。

ゾーン2とゾーン3の並べ方は通りであるから、

である。

④最後に順列自身の転倒数を加えておしまい。

実装

ACコード

void solve()
{
    int N = cin.nextint;
    var F = new ModInt[N + 1];
    var P = new ModInt[N + 1];
    F[0] = 1;
    var f = ModInt.Pow(4, mod - 2);

    for (int i = 1; i <= N; i++)
    {
        F[i] = F[i - 1] * i;
        P[i] = F[i] * i * (i - 1) * f;
    }

    var BIT = new FenwickTree(N); //1-indexed, sumは閉区間
    ModInt inv1 = 0; //ゾーン1の転倒数       
    ModInt marge = 0; //ゾーン1と23のマージコスト
    ModInt ans = 0;

    for (int i = 0; i < N; i++)
    {
        int p = cin.nextint;
        BIT.Add(p, 1);
        var cnt = p - BIT[p];//ゾーン2の候補数

        //ゾーン3の転倒数
        var inv3 = P[N - i - 1];

        ans += cnt * inv3; //ゾーン3合計
        ans += cnt * (cnt - 1) / 2 % mod * F[N - i - 1]; //ゾーン2と3のマージ
        ans += cnt * (inv1 + marge) * F[N - i - 1]; //ゾーン1と23のマージ


        inv1 += BIT[p + 1, N];

        marge += cnt;
        marge -= BIT[p + 1, N];

    }

    WriteLine(ans + inv1);
}

まとめ

一般人は2時間では解けないのでなるほど5時間コンテストらしい問題だなあと思う。(考え始めてから6時間はかかりましたが)