AtCoder Regular Contest 097：E - Sorted and Sorted

問題
解法
解答

問題

解法

次の DP を考える：

dp(i, j) := 白いボールを 1 ~ i 番までソートし，黒いボールを 1 ~ j 番までソートしたときの，残っている 2 * N - (i + j) 個のボールをそれぞれの色でソートするのにかかる操作回数の最小値

この DP を更新する漸化式はいたってシンプルで次のようになる：

dp(i, j) = min( dp(i + 1, j) + (i + 1 番の白いボールを (i + j + 1) 番目に持ってくるのにかかる操作回数), dp(i, j + 1) + (j + 1 番の黒いボールを (i + j + 1) 番目に持ってくるのにかかる操作回数) )

となる．ここでこの問題の本質は「k 番目の白い・黒いボールを任意の場所に置くときにかかる操作回数」を求めることになる．

あり得る (i, j) の組全てに対しこれを求める．白い・黒いボールを 1 ~ i, 1 ~ j 番までソートしたときの 2 * N 個のボールの並び方は一意に定まるので，前後の操作の手順は関係ない（白黒白とソートしたか，黒白白とソートしたかなど，i + j 個のソートの順番に関係ない）．

ここで，i + j 個ソートした直後のボールの情報が分かれば，これは求めることが出来る．このソート列の直後のボールは元のボールの列から 1 ~ i, 1 ~ j 番までの白い・黒いボールを消したときの先頭のボールになる．つまり，元のボールの列のうち i より大きい白いボールか j より大きい黒いボールのどちらかになる．これは前計算をしておき，両者の位置の min を取ることで求まる．

これでソート列の直後のボールが元にあった位置が求まった．この位置と新たにソート列に加える白い・黒いボールが元にあった位置（これも前計算でメモしておく）の間からボールがいくつ前のソート列に移動したか（言い変えると，無くなったか）を求めたい．これは，この区間の中の i, j 以下の白い・黒いボールの数を数えればよいので，前計算で累積和を求めておき，求めることが出来る．これで (i, j) に対する白い・黒いボールをソート列に追加するときに必要な操作回数が求まった．

後は最初に書いた DP を実行すればよい．前計算 O(N^2)，DP O(N^2) となる．