Sorted and Sorted [AtCoder Regular Contest 097 E] - はまやんはまやんはまやん

https://beta.atcoder.jp/contests/arc097/tasks/arc097_c

前提知識

考察

1. ぱっと見て何も思いつかない
2. 制約を見てみるとN=2000になっているのでO(N^2)を疑う
3. 本当に何も思いつかないので、サンプルを使って人力で解いてみる
4. 白と黒について1から順番に先頭に取ってくる操作を行っていけばいい
5. 重要考察「白のwまで、黒のbまで先頭に取ってきた場合に残るボールの列は一意に定まる」
6. つまり、白と黒のどの数まで先頭に取ってきたかで状態を纏めることができそう
7. それをkeyとしたDPだとO(N^2)で、更新もO(1)で行けそう

解法

https://beta.atcoder.jp/contests/arc097/submissions/2500398

DPをメモ化再帰で解いた。
「f(b,w) := 黒の数bまで、白の数wまで先頭に持って来ている場合の操作回数最小値」
この場合に出来る遷移は2種類
遷移は「黒の次の数b+1を先頭に持ってくる場合」と「白の次の数w+1を先頭に持ってくる場合」である。
　
「黒の次の数b+1を先頭に持ってくる場合」
黒の次の数b+1を先頭に持ってくる場合に必要なスワップ回数は先頭から黒のb+1までで、先頭に持ってきてない数の個数と等しい。
黒のb+1の座標をidxB[b+1]とすると、

int cnt = 0;
rep(i, 0, idxB[b + 1]) {
    if (C[i] == 'B' and b < A[i]) cnt++;
    if (C[i] == 'W' and w < A[i]) cnt++;
}

のように書ける。下のコードのコメントアウト部分。
しかし、計算ではO(1)でやりたいので、累積和を使ってこの部分を高速化する。
「smB[i][j] := ボールの[0,j]番目で色が黒、数がi以上である個数」
「smW[i][j] := ボールの[0,j]番目で色が白、数がi以上である個数」
以上の累積和を用意しておくと、

int cnt = 0;
if (0 <= idxB[b + 1] - 1) cnt += smB[b + 1][idxB[b + 1] - 1];
if (0 <= idxB[b + 1] - 1) cnt += smW[w + 1][idxB[b + 1] - 1];

このように高速化できる。
　
「白の次の数w+1を先頭に持ってくる場合」
同様に計算しよう。
　
あとは、適切にメモ化してやれば答え。

int N;
char C[4020];
int A[4020];
int smB[2020][4020];
int smW[2020][4020];
int idxB[2020];
int idxW[2020];
//---------------------------------------------------------------------------------------------------
int memo[2020][2020];
int f(int b, int w) {
    if (b == N and w == N) return 0;
    if (0 <= memo[b][w]) return memo[b][w];
 
    int res = inf;
 
    if (b != N) {
        /*int cnt = 0;
        rep(i, 0, idxB[b + 1]) {
            if (C[i] == 'B' and b < A[i]) cnt++;
            if (C[i] == 'W' and w < A[i]) cnt++;
        }*/
 
        int cnt = 0;
        if (0 <= idxB[b + 1] - 1) cnt += smB[b + 1][idxB[b + 1] - 1];
        if (0 <= idxB[b + 1] - 1) cnt += smW[w + 1][idxB[b + 1] - 1];
        
        chmin(res, f(b + 1, w) + cnt);
    }
 
    if (w != N) {
        /*int cnt = 0;
        rep(i, 0, idxW[w + 1]) {
            if (C[i] == 'B' and b < A[i]) cnt++;
            if (C[i] == 'W' and w < A[i]) cnt++;
        }*/
 
        int cnt = 0;
        if (0 <= idxW[w + 1] - 1) cnt += smB[b + 1][idxW[w + 1] - 1];
        if (0 <= idxW[w + 1] - 1) cnt += smW[w + 1][idxW[w + 1] - 1];
        chmin(res, f(b, w + 1) + cnt);
    }
 
    return memo[b][w] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 2 * N) cin >> C[i] >> A[i];
 
    rep(i, 0, 2 * N) {
        if (C[i] == 'B') smB[A[i]][i]++;
        else smW[A[i]][i]++;
    }
    rep(i, 0, N + 5) {
        rep(j, 1, 2 * N) smB[i][j] += smB[i][j - 1];
        rep(j, 1, 2 * N) smW[i][j] += smW[i][j - 1];
    }
    rep(j, 0, 2 * N) {
        rrep(i, N+4, 0) smB[i][j] += smB[i + 1][j];
        rrep(i, N+4, 0) smW[i][j] += smW[i + 1][j];
    }
 
    rep(i, 0, 2 * N) {
        if (C[i] == 'B') idxB[A[i]] = i;
        if (C[i] == 'W') idxW[A[i]] = i;
    }
 
    rep(i, 0, N + 1) rep(j, 0, N + 1) memo[i][j] = -1;
    cout << f(0, 0) << endl;
}