Sortedatcoder.jp600埋め!スマートな解説ではなく、遠回りなACまでの流れを書きます。(N<=2000)のいずれかが書かれた白黒のボールが1つずつ、適当に並んでいる.これらのボールを並び替えて、それぞれの色のボールが昇順になるようにする。隣り合うボールを入れ替える処理を行える。最小何回で実現できるか。→BITでは?小さい要素から順に左端まで運ぶ。この時のコストは、動かしたいボールより左にある未処理のボールの数。(BITを使うと処理/未処理の更新と未処理のボールのカウントが簡単に行える。)白と黒の候補のうち、コストの低い方を動かす。サンプル通ったので提出。→WA次の考察コストの大きな要素を先に運んだ方が良かったりする?例を考える。233211(白は読めないので赤で表示)黒の1より赤の123の方が優先されると、合計コストは11。最初に黒の1を動かすと合計コスト8で処理できる。考察は振り出しに戻る。「最後に動かした白黒それぞれのボールが同じなら、未処理のボールの配置は同じ。)」ということに気づく。233211の場合は次のような遷移で表現できる。これはN^2のDPですね...。最後の考察それぞれの状態において、ボールを端まで動かすコストが求まればDPが書ける。ボールを動かすコストの計算はO(N)...?ここでBITを思い出して、DPのループを回しながらBITも更新していけば、ボールを動かすコストも簡単に計算できることに気づく。