ソート

問題概要 問題へのリンク 長さ$N$の文字列 $S$ が与えられる．$S$ に現れる文字は B と P だけ． 次の操作によって，B を左に P を右に寄せ $S$ を BB...BPP...P という形にする． 操作の最小回数を求めよ． $S$ の長さ3の部分列をとり，その部分の B を左に，P を右に寄せる． つまり，1回の操作は，以下のいずれか: (あ) PPB $\to$ BPP (い) PBP $\to$ BPP (う) PBB $\to$ BBP (え) BPB $\to$ BBP 制約 $3 \leq N \leq 2\times10^5$ 解 tutorialへのリンク 略解．click to open 奇数番のみ，偶数番のみの列を考えると， 操作は，次のいずれかになっている: (ア) 奇数列の隣接入替，偶数列の隣接入替 (あ, う) (イ) 奇数列と偶数列の B, P の入替 (い，え) 全体としてみたときの転倒数を $r$ とする．(ア)では転倒数が2減り， (イ) では転倒数が1減る． 最終形を考えると，奇数列，偶数列の B, P の個数は決まっている． だから，(イ) の最低必要な回数 $x$ が決まる． 「最初に (イ) を $x$ 回行って，あとの操作はすべて (ア)」が実現できれば， それ以上回数は減らせない．...