E - Sorted and Sorted | AtCoder Regular Contest 097

隣接要素同士の交換しかできないのだから、もし白または黒のみであれば、最小の操作回数は転倒数に等しい。

この問題では、白と黒の２色の並び方ごとに操作回数が異なる。しかし、白と黒の並びが定まれば、操作回数は一意に定まる。なぜなら、各並び方について、白黒区別なく先頭から1~2Nと番号をつけ直せば、ただの順列のソートであるため。

先頭の要素からソートしていく。

dp[w][b]:=「先頭へ詰めて白1~w, 黒1~bをソート済みのときの最小の操作回数」

とおく。先頭からw+b個はソート済みということ。このとき、次に白、黒のどちらがきても dp[w+1][b]またはdp[w][b+1]のどちらかを更新することで対応できる。dp[N][N]が解。

状態(w, b)で次に白または黒をw+b+1番目まで持ってくるときのコストを知る必要がある。対称性から、次に白が来る場合だけを考える（黒の場合も同様）。w=b=0のとき、白1番がk番目にあるとすると、コストk-1で先頭まで持って来れる。状態から(w, b)の場合は、kより左にあってソート済みの要素を超えて左に行く必要がないのでコストはkより左にあってソート済みでない要素の個数。左にあってソート済みでない要素の個数はBinary Indexed TreeでDPのループごとに計算できる。

template<class Val>
struct BinaryIndexedTree {
    int n;
    vector<Val> t;
    BinaryIndexedTree() {}
    BinaryIndexedTree(int _n) :n(_n + 1), t(_n + 1) {}
    void add(int k, Val val) {
        k++;
        while (k < n) {
            t[k] += val;
            k += (k&-k);
        }
    }
    void set(int k, Val val) {
        add(k, -sum(k, k + 1));
        add(k, val);
    }
    Val sum(int k) {
        Val r = 0;
        while (k > 0) {
            r += t[k];
            k -= (k&-k);
        }
        return r;
    }
    Val sum(int l, int r) {
        return sum(r) - sum(l);
    }
};
typedef BinaryIndexedTree<int> BIT;

const ll INF = 1ll << 60;
ll dp[2001][2001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    int N;
    cin >> N;
    vector<char> C(2*N);
    vi A(2*N), wk(N), bk(N);
    rep(i, 2*N) {
        cin >> C[i] >> A[i];
        --A[i];
        if (C[i] == 'W')wk[A[i]] = i;
        else bk[A[i]] = i;
    }

    rep(i, N + 1)rep(j, N + 1)dp[i][j] = INF;
    dp[0][0] = 0;
    BIT bit(2 * N);
    rep(i, 2 * N)bit.add(i, 1);

    rep(w, N+1) {
        rep(b, N+1) {
            if (w < N) {
                ll x = bit.sum(wk[w]);
                smin(dp[w + 1][b], dp[w][b] + x);
            }
            if (b < N) {
                ll x = bit.sum(bk[b]);
                smin(dp[w][b + 1], dp[w][b] + x);
            }
            if (b < N)bit.add(bk[b], -1);
        }
        rep(b, N)bit.add(bk[b], 1);
        if(w<N)bit.add(wk[w], -1);
    }

    cout << dp[N][N] << endl;
}