Codeforces Round #204 (Div. 1) B. Jeff and Furik

気づくべきことはすぐ気づいたのに漸化式間違えて時間食った。

問題

codeforces.com

解法

要するに, 反転数が 0 になるために何回操作が必要か, という問題です。

方針としては, とにかく反転数を減らすのが良いです。状態は反転数のみで記述できて, 反転数が n の時ソートさせるために必要な操作回数を pn すると,

という漸化式が成り立ちます。これは簡単に計算できて,

です。初期条件 を用いると
n が偶数なら pn = 2n
n が奇数なら pn = 2n+1
です。

一応ちょっと補足すると, ランダムに操作する側(Furik)が 反転数を減らせないような操作をすることになることはありえません。これは, Jeff は必ず反転数が減るような操作をするので, 反転数を減らせないような操作をするのは, 完全にソートされて操作が終了した時しかありえないからです。よって, 上の漸化式は常に成り立ちます。

const int MAXN = 3333;
int p[MAXN];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (p[i] > p[j]) cnt++;
        }
    }
    if (cnt%2 == 0) {
        cout << 2*cnt << endl;
    } else {
        cout << 2*cnt-1 << endl;
    }
    return 0;
}