乐胖代购免代理版

600 にしちゃムズイ。

問題概要

(白, 1), (白, 2), ..., (白, N), (黒, 1), (黒, 2), ..., (黒, N) の 2N 個の要素の順列が与えられる。「隣同士を swap する」を最小回数行うことで、「白」についても「黒」についてもソートされた状態にせよ。

制約

1 <= N <= 2000

解法

一色だけなら「バブルソートの交換回数」や「転倒数」と呼ばれているやつなん。BIT や分割統治法でできるん。

今回は O(N²) が間に合うということで、なんとなく DP っぽい。重要な考察として、最終状態における「白」「黒」の配置を決めれば、最小 swap 回数は一意に決まる。

なので、左から見て途中状態での「白個数」「黒個数」を決めたときの最小 swap 回数をメモして行く DP が自然に浮かぶ

dp[ i ][ j ] := 左から順に白が i 個、黒が j 個にな状態を達成するのに必要な最小 swap 回数

dp[ i+1 ][ j ] = min(dp[ i+1 ][ j ], dp[ i ][ j ] + (白, i) より左に i より大きい白と j 以上の黒が何個あるか)

dp[ i ][ j+1 ] = min(dp[ i ][ j+1 ], dp[ i ][ j ] + (黒, j) より左に j より大きい黒と i 以上の白が何個あるか)

あとは、「(白, i) より左に i より大きい白と j 以上の黒が何個あるか」といったものを前処理によって求めておけば良い。全体として O(N²) で計算できる。

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int N;
vector<pair<char,int> > vec;

// dp[i][j] := 左から (B, 0), ..., (B, i-1)、(W, 0), ..., (W, j-1) を敷き詰めるまでの最短 swap 数
int dp[2100][2100];

int main() {
    cin >> N;
    vec.resize(N*2);
    for (int i = 0; i < N*2; ++i) {
        cin >> vec[i].first >> vec[i].second;
        --vec[i].second;
    }
    
    // (B, i) の前に (B, iより大きい) + (W, j以上) が何個あるか
    vector<vector<int> > black(N, vector<int>(N+1, 0));
    
    // (W, i) の前に (W, iより大きい) + (B, j以上) が何個あるか
    vector<vector<int> > white(N, vector<int>(N+1, 0));
    
    vector<int> bnum(N, 0);
    vector<int> wnum(N, 0);
    for (int k = 0; k < N*2; ++k) {
        char c = vec[k].first;
        int num = vec[k].second;
        vector<int> wsum(N+1, 0), bsum(N+1, 0);
        for (int l = N; l > 0; --l) {
            bsum[l-1] = bsum[l] + bnum[l-1];
            wsum[l-1] = wsum[l] + wnum[l-1];
        }
        for (int l = N+1; l > 0; --l) {
          if (c == 'B') black[num][l-1] = wsum[l-1] + bsum[num+1];
          if (c == 'W') white[num][l-1] = wsum[num+1] + bsum[l-1];
        }
        if (c == 'B')  bnum[num]++;
        else wnum[num]++;
    }
    
    /* DP */
    for (int i = 0; i < 2100; ++i) for (int j = 0; j < 2100; ++j) dp[i][j] = 1<<29;
    dp[0][0] = 0;
    for (int i = 0; i <= N; ++i) {
        for (int j = 0; j <= N; ++j) {
            if (i < N) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + black[i][j]);
            if (j < N) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + white[j][i]);
        }
    }
    cout << dp[N][N] << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ARC 097 E - Sorted and Sorted (黄色, 600 点)

問題概要

制約

解法