問題概要

1からNまでの数字が書かれた，黒・白のボールがある．この2N個のボールを，それぞれの色について数字が昇順になるように並べ替える．隣同士のボールの交換を繰り返して並べ替えを行うとき，最小の交換回数を求める．

解法概要

「隣同士の交換」「交換回数」とか言っているので，BITによる転倒数の計算が使えそうという気持ちになる．

ただし，ボールは2色ある．問題に書いてある並べ替えの条件は数字についてだけで，黒・白の2色がどのように並ぶべきかはわからない．

そこで，次のようなDPテーブルを定義する

dp[i][j] ($ 0 \leq i,j \leq n $) : 黒いボールは数字iまで，白いボールは数字jまでのボールが問題の条件を満たす順に並ぶために必要な最小の交換回数

dp[i][j]から遷移できるのはdp[i+1][j]，dp[i][j+1]のみであることを利用しつつ，BITで転倒数を求める過程でDPテーブルを埋めていく．

ソースコード

#include<iostream>
#include<utility>
#include<vector>
#include<climits>

using namespace std;

typedef pair<int, int> Pii;

class BIT {
    public:
    int n;
    int bit[1000001];
    
    BIT(int n){
        this->n = n;
        fill(bit, bit+n, 0);
    }

    void add(int idx, int x){
        for(int i=idx;i<=this->n;i+=i&-i) bit[i] += x;
    }

    //bit[1]からbit[end]までの和 (閉区間)
    int sum(int end){
        int ret = 0;
        for(int i=end;i>=1;i-=i&-i) ret += bit[i];
        return ret;
    }
};


int main() {
    std::ios::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;

    int mp[2][n+1];
    char c;
    int num;
    for(int i=1;i<=2*n;++i){
        cin >> c >> num;
        mp[(c=='W'?0:1)][num] = i;
    }

    vector< vector<int> > dp(n+1, vector<int>(n+1, INT_MAX));
    dp[0][0] = 0;
    BIT tree = BIT(2*n+1);

    for(int i=0;i<=n;++i){
        if(i) tree.add(mp[0][i], 1);

        for(int j=0;j<=n;++j){
            if(j) tree.add(mp[1][j], 1);
            if(i != n) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (i+j-tree.sum(mp[0][i+1])));
            if(j != n) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + (i+j-tree.sum(mp[1][j+1])));
        }

        for(int j=1;j<=n;++j) tree.add(mp[1][j], -1);
    }

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

感想

BIT使えば良さそうまでは本番でも思いついたけど，DPとはまいったな〜．でも書いてみたらすごく綺麗に解けて感動した．これからは「順番を固定さえできれば解けるのにな〜」という気持ちになったらDPを考えてみることにしよう．

ちなみに貰うDPで書くよりも配るDPで書くほうが綺麗に書けた (主にBITのクエリ関連)．

NoiminのNoise

AtCoder Regular Contest 097 E - Sorted and Sorted

問題概要

解法概要

ソースコード

感想