Submission #4016762

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <set>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <stack>
#include <complex>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

int N;
vector<P> ball;
int b[2100];   //それぞれの番号が何番目にあるか
int w[2100];
int w_offset[2100][2100];
int b_offset[2100][2100];
int dp[2100][2100];

int main(){
    cin >> N;
    for(int i = 0; i < 2*N; i++){
        char c; cin >> c;
        int a;  cin >> a;
        if(c == 'W'){
            w[a] = i+1;
            ball.emplace_back(P(0, a));
        }
        else{
            b[a] = i+1;
            ball.emplace_back(P(1, a));
        }
    }
    for(int i = 0; i <= N; i++){
        fill(w_offset[i], w_offset[i]+N+10, 0);
        fill(b_offset[i], b_offset[i]+N+10, 0);
        fill(dp[i], dp[i]+N+10, 0);
    }

    for(int i = 1; i <= N; i++) {
        int w_plus = 0;
        int b_plus = 0;
        for (int j = i - 1; j > 0; j--) {
            if (w[i] < w[j]) {
                w_plus++;
            }
            if (b[i] < b[j]) {
                b_plus++;
            }
        }
        w_offset[0][i] = w_plus;
        b_offset[0][i] = b_plus;
    }

    // bがiだけ進んだ時にwがどれくらいずれるか
    for(int i = 1; i <= N; i++){
        int b_pos = b[i];
        for(int j = 1; j <= N; j++){
            if(b_pos > w[j]){
                w_offset[i][j] = w_offset[i-1][j] + 1;
            }
            else{
                w_offset[i][j] = w_offset[i-1][j];
            }
        }
    }
    // wがiだけ進んだ時にbがどれくらいずれるか
    for(int i = 1; i <= N; i++){
        int w_pos = w[i];
        for(int j = 1; j <= N; j++){
            if(w_pos > b[j]){
                b_offset[i][j] = b_offset[i-1][j] + 1;
            }
            else{
                b_offset[i][j] = b_offset[i-1][j];
            }
        }
    }

    for(int w_i = 1; w_i <= N; w_i++){
        int move = w[w_i] + w_offset[0][w_i] - w_i;
        // cout << w_i << " " << w_offset[0][w_i] << " " << move << endl;
        dp[w_i][0] = dp[w_i-1][0] + move;
    }
    for(int b_i = 1; b_i <= N; b_i++){
        int move = b[b_i] + b_offset[0][b_i] - b_i;
        // cout << b_i << " " << w_offset[0][b_i] << " " << move << endl;
        dp[0][b_i] = dp[0][b_i-1] + move;
    }
    for(int b_i = 1; b_i <= N; b_i++){
        for(int w_i = 1; w_i <= N; w_i++){
            //w_i+b_i番目に置く。
            int w_move = w[w_i] + w_offset[b_i][w_i] - (w_i+b_i);  //wを置くとき。
            int b_move = b[b_i] + b_offset[w_i][b_i] - (w_i+b_i);  //bを置くとき。
            dp[w_i][b_i] = min(dp[w_i-1][b_i] + w_move, dp[w_i][b_i-1] + b_move);
            // cout << dp[w_i][b_i] << " ";
        }
        // cout << endl;
    }

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


    return 0;

}

Submission Info

Judge Result