問題概要

問題へのリンク

長さ$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$ 回行って，あとの操作はすべて (ア)」が実現できれば， それ以上回数は減らせない．

最初に(イ）を $x$ 回行えることは，次のようにわかる． たとえば，奇数列の B が多すぎる場合．位置 $2i$ と $2i + 1$ が PB になっているところが どこかにある．その前が P で 後ろが B だと，それらを含めた並びは PPBB になってしまって (イ) が適用できないが，この場合には，偶数列と奇数列に B があって，数には貢献していないので，どこか他の箇所を探せる． それ以外の場合には (イ) が適用できる．これを必要なだけ繰り返す．