ICPCアジア地区横浜大会2018 G問題 : What Goes Up Must Come Down

問題. What Goes Up Must Come Down

非負整数列 $a = (a_1, \ldots, a_n)$ が与えられる． $a$ の隣り合う2要素を交換するという操作を繰り返して $a$ を山型にしたい．ただし，数列 $(b_1, \ldots, b_m)$ が山型であるとは，ある要素 $1 \le i \le m$ が存在して， $b_1 \le b_2 \le \ldots \le b_{i-1} \le b_i \ge b_{i+1} \ge \ldots \ge b_m$ となることである．数列 $a$ を山型にするための交換回数の最小値を求めよ．

制約： $1 \le n \le 100,000$ ，　 $1 \le a_i \le 100,000$

解法. BIT

まず初めの観察として， $a$ の最小値で最も端にある要素 $a_i$ に着目したとき， $a$ の任意の操作後の山型な数列に対して， $a_i$ はその数列の左端か右端のどちらかにある．また，操作後の最適な山型な数列に対しては， $a_i$ は最も近い左端か右端になることが分かる．この操作によって， $a_i$ 以外の2要素間の位置関係は保たれており，これを再帰的に行うと答えが求まる．すなわち，操作済みではない部分列に対して，その最小の要素で最も部分列の端にあるものを近い端に移動するということを再帰的に行う．
このアルゴリズムは Binary Indexed Tree (BIT) を用いて愚直に計算すると $O(n^2 \log n)$ で計算することができるが，この再帰的な移動で着目している要素が何かを考えるとより高速に計算できる．各 $a_i$ に対して，上で再帰的に行ったときの操作回数は， $a$ 上で $i$ より左にあって $a_i$ よりも大きい値の数と， $i$ より右にあって $a_i$ より大きい値の数の最小値と等しくなる． $i$ より左にあって $a_i$ よりも大きい値の数は，BIT bit[i] の引数 $i$ を $a$ の要素の値として，BIT の値 bit[i] を $a_i$ よりも左にあって値が $i$ となる $a$ の要素数として，左から更新しながら計算することによって求めることができる．同様に，右にある値も右から更新しながら計算できる．よって，この問題では $a_i$ の上限と $n$ の上限が等しいので，全体で $O(n \log n)$ 時間で答えを求めることができる．

計算時間： $O(n \log n)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template <class T>
struct FenwickTree {
    const int n;
    std::vector<T> bit;

    FenwickTree(int _n = 0) : n(_n), bit(n + 1, 0) {}

    T sum(int r) const {
        T res = 0;
        for (r = r - 1; r >= 0; r = (r & (r + 1)) - 1) res += bit[r];
        return res;
    }
    T sum(int l, int r) const { return sum(r) - sum(l); }
    void add(int idx, const T &w) { for (; idx < n; idx |= idx + 1) bit[idx] += w; }
    int size() const { return n; }
};

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];

    const int max_a = *max_element(a.begin(), a.end()) + 1;
    FenwickTree<int> l(max_a), r(max_a);
    vector<int> num(n);
    for (int i = 0; i < n; ++i) {
        num[i] = l.sum(a[i] + 1, max_a);
        l.add(a[i], 1);
    }
    for (int i = n - 1; 0 <= i; --i) {
        num[i] = min(num[i], r.sum(a[i] + 1, max_a));
        r.add(a[i], 1);
    }

    cout << accumulate(num.begin(), num.end(), 0ll) << endl;

    return 0;
}

まとめ

初め最小値ではなく最大値を考えてムムッとなっていた．