CROC 2016 - Elimination Round B. Mischievous Mess Makers

各要素が 1,2,...,n の数列がある。k 回まで任意の 2 要素をスワップできるので、転倒数を最大化せよ。

なお、転倒数というのは i<j かつ a[i]>a[j] となるような対 (i,j) の個数のことである。

転倒数が最大になるのは元の数列の逆、つまり n,n-1,n-2,...,2,1 のときである。そのため、この状態に近づくようにスワップしていけばいい。

ただしスワップ回数に上限があるので、適当な順序でスワップしてしまうと最適解が得られない。最大化するには (1,n),(2,n-1),(3,n-2),... の順でスワップする必要がある。

スワップする毎に転倒数は次のような変化をする。

f:id:pekempey:20160319133059p:plain

この増加は等差数列になっているため等差数列の和の公式が使えるが、制約が緩いので愚直に足しても間に合う。BIT を使って求めてもいい。

簡単だけどオーバーフローには気をつけたい。