[AtCoder] 第一回日本最強プログラマー学生選手権-予選-

問題

方針

転倒数

転倒数を求めるアルゴリズムはマージソートを利用したものや BIT を使ったものがありますが、今回はデータ数が小さいので、\( O(N^2)\) の計算量が間に合います。\( A \) の転倒数を \( s_1 \) とします。

全体の配列の転倒数

ここで、\( C_i = A = (A_0, A_1, \cdots, A_{N-1})\) として、\( B = (C_1, C_2, \cdots, C_K) \) と表現します。任意の二組の配列の転倒数 \( s_2 \) を次のように定義します。\( s_2 \) は、\( A_i > A_j \ ( 0 \leq i < N \wedge 0 \leq j < N) \) を満たす \( i, j \) の組み合わせとします。任意の二組の組み合わせは、\( {}_{N} \mathrm{ C }_{2} \) 通りあるので、全体の転倒数は、

\[s_1K + s_2{}_{N} \mathrm{ C }_{2} \]

となります。

コード