ARC097 E : Sorted and Sorted(600)
作成日：2018.09.24
最終更新日：2018.09.24
問題概要
黒($B$)と白($W$)のボールがそれぞれ$N$個あり、各色のボールには$1$から$N$まで異なる整数が1つずつ書かれている。
合わせて$2N$個のボールが1列に並んでおり、左から$i$番目は$a_i$が書かれている色$c_i$のボールである。
操作「隣り合う2つのボールを入れ替える」を繰り返すことで、各色ごとに番号が小さいボールほど左にある状態にしたい。
これを達成するために必要な操作の回数の最小値を求めよ。
制約
$1 \leq N \leq 2000$
$1 \leq a_i \leq N$
$c_i = 'B','W'$
$i \neq j$ならば$(a_i,c_i) \neq (a_j,c_j)$
考え方
ボールが1色しかなければ、転倒数を求める問題である。
転倒数を求めるには、前から数列を見ていき、今見ている位置とそこに入るべき数が今ある位置の距離の総和を計算していけば良い。
そこでボールが2色の時にも、これと同様に求められないかを考える。
前から順番に見ていくと、ある位置に決まり得るボールは黒と白それぞれ$1$種類以下である。
すなわち黒と白それぞれ番号$b$,$w$のボールまで位置を決めた(まだ1つも決めていなければ$0$)とすると、入り得るボールは$(b+1)$番の黒($b \neq N$の時)と$(w+1)$番の白($w \neq N$の時)ということである。
また、今見ている位置(0-indexed)は$b+w$である。
さらにボールが今ある位置は、そのボールが初めにあった位置$p$より後ろにあったボールのうち、すでに位置が決まったものの数$m_p$だけ初めの位置から後ろにずれている。
すなわち動かすべき距離は、$p-(b+w)+m_p$である。
ところで、$b+w-m_p$は初めに位置$p$より前にあったボールのうち位置が決まったものの数$s_p$に等しい。
この$s_p$を求めるには転倒数を求める時と同様に、位置が決まったボールが初めにあった位置に$1$を加算し、先頭から位置$p$までの累積和をとれば良い。
これはBinary Indexed Tree(BIT)を用いれば$O(log N)$で求められる。
但し$b,w$の組をすべて試す都合上、黒と白のボールそれぞれで$s_p$を求めるBITを持つべきである。
($s_p$を考えることで定数倍改善及びコード量微減の効果があるが、$m_p$のまま考えても同様に求められるので問題ない)
以上より、黒と白それぞれ番号$b$,$w$のボールまで入れた状態$\langle b,w \rangle$を持つDPを行えば良いことが分かる。
具体的には$\langle 0,0 \rangle = 0$,$\langle b,w \rangle$$=min(\langle b-1,w \rangle$$+ p_{B,b}$$- s_{p_{B,b}}$,$\langle b,w-1 \rangle$$+ p_{W,w}$$- s_{p_{W,w}})$($b-1$や$w-1$が負となるものは$\infty$とする)である。
但し$p_{c,x}$は$x$番の書かれた色$c$のボールの位置である。
このDPの計算量は$O(N^2 log \: N)$であるから十分高速である。
ソースコード
マクロ等はこちら
BIT<T>
void add(int a , T b)
$a$番目の要素に$b$を加える
T get(int a)
先頭(0番目)から$a$番目の要素までの累積和を取得する
const int MC = 2003;
int N,b[MC],w[MC];
int dp[MC][MC];
int main(){
cin >> N;
repp(i,0,2*N){
char c; int a; cin >> c >> a;
(c=='B'?b:w)[a-1] = i;
}
repp(i,0,N+1) fill(dp[i],dp[i]+MC,1e9);
dp[0][0] = 0;
BIT<int> bit0;
repp(i,0,N+1){
BIT<int> bit1;
repp(j,0,N+1){
if(i < N) dp[i+1][j] = min(dp[i+1][j] , dp[i][j] + b[i] - bit0.get(b[i]) - bit1.get(b[i]));
if(j < N) dp[i][j+1] = min(dp[i][j+1] , dp[i][j] + w[j] - bit0.get(w[j]) - bit1.get(w[j]));
bit1.add(w[j],1);
}
bit0.add(b[i],1);
}
cout << dp[N][N] << endl;
return 0;
}解法まとめ
黒と白それぞれ番号$i$,$j$のボールまで入れた(まだ1つも入れていなければ$0$とする)状態$\langle i,j \rangle$を持つDPを行う。
各状態における値は$\langle 0,0 \rangle = 0$,$\langle i,j \rangle$$=min(\langle i-1,j \rangle$$+ b_i$$- s_{b_i}$,$\langle i,j-1 \rangle$$+ w_j$$- s_{w_j})$($i-1$や$j-1$が負となるものは$\infty$とする)であり、答えは$\langle N,N \rangle$である。
但し$b_i$,$w_j$はそれぞれ番号$i$の黒いボール、番号$j$の白いボールの初めの位置であり、$s_k$は初めに位置$k$より前にあったボールのうちすでに位置が決まったものの数である。(11-23行)
$s_k$は、黒と白それぞれ別にBinary Indexed Treeを用いて求めたものの和として求める。(17-19,21行)