ARC097 E - Sorted and Sorted

問題ページ

解法

転倒数が答えになるので転倒数の定義を考える。最初の数列をA、最終状態の数列をBとする。(転倒数) = (A[ia]=B[ib]=x,A[ja]=B[jb]=yとしたときにia<jaかつib>jbとなるペア(x,y) (x<y)の数) となる。転倒数は線形和で書くことができ(転倒数) = sum(ペアの片方xを固定したときの転倒数)となる。
最終状態で小さい方から決定していくとすると現在追加するボールに関連する転倒数は過去・未来の挿入順によらず決定できる。小さい順に追加していくと考えて挿入DPを行う。dp[i][j] = (黒のi,白のjまで置いたときの転倒数のmin)としたDPを行う。このDPの遷移は dp[i][j] = min(dp[i-1][j]+黒のiについてのコスト,dp[i][j-1]+白のjについてのコスト) となる。黒のi、白のjについての転倒数が高速に知りたいので前計算しておく。cost_b[i][j] = 初期状態で黒のiより右にある 黒のi未満 or 白のj以下 の個数、cost_w[i][j] = 初期状態で白のjより右にある 黒のi以下 or 白のj未満 の個数が計算できればよい。これは白のボール、黒のボールそれぞれについてi以下のボールの個数を管理するBITを持っておいて後ろから見ていくことでO(N^2logN)で実現できる。

転倒数は線形和で書ける
挿入順が影響しないときは挿入DPがつよい

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
// #define int ll
using PII = pair<int, int>;
 
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
 
template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
 
template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) { 
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }
 
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) {is >> x;} return is;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'['; for(T i: a) {out<<i<<',';} out<<']'; return out;
}
 
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const int MOD = 1000000007;

template <typename T>
class BIT {
private:
  // データ
  vector<T> bit;
  // 単位元, 要素数
  T neutral = 0;
  // 更新クエリ, 区間クエリ
  function<T(T,T)> f = [](const T l, const T r) -> T { return l+r; },
                   g = [](const T l, const T r) -> T { return l+r; };
public:
  // 初期化
  BIT(int n_ = 1e5) { init(n_); }
  void init(int n_ = 1e5) { bit.assign(n_+1, neutral); }
  // iに対する点更新クエリ
  void update(int i, T w) {
    for(int x = i+1; x < bit.size(); x += x&-x) bit[x] = f(bit[x], w);
  }
  // [0,i]に対する区間クエリ
  T query(int i) {
    T ret = neutral;
    for(int x = i+1; x > 0; x -= x & -x) ret = g(ret, bit[x]);
    return ret;
  }
};

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  ll n;
  cin >> n;
  vector<char> c(2*n);
  vector<ll> a(2*n);
  REP(i, 2*n) cin >> c[i] >> a[i], a[i];

  auto cost_b = make_v<ll>(n+1, n+1);
  auto cost_w = make_v<ll>(n+1, n+1);
  BIT<ll> black(n+1), white(n+1);
  for(ll i=2*n-1; i>=0; --i) {
    if(c[i]=='B') {
      REP(j, n+1) {
        cost_b[a[i]][j] = black.query(a[i]-1) + white.query(j);
      }
      black.update(a[i], 1);
    } else {
      REP(j, n+1) {
        cost_w[j][a[i]] = black.query(j) + white.query(a[i]-1);
      }
      white.update(a[i], 1);
    }
  }

  auto dp = make_v<ll>(n+1, n+1);
  fill_v(dp, INF);
  dp[0][0] = 0;
  REP(i, n+1) REP(j, n+1) {
    if(i) chmin(dp[i][j], dp[i-1][j] + cost_b[i][j]);
    if(j) chmin(dp[i][j], dp[i][j-1] + cost_w[i][j]);
  }
  cout << dp[n][n] << endl;

  return 0;
}