ABC 401-500/ABC421C - Alternated - 競技プログラミング用 知識集積所

---

問題

ABC421C

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）※

考え方

A同士やB同士を入れ替えるメリットは何もない。
よって、前からi個目のAを、前からi個目のA用目標地点に移動する貪欲法※でよい。

そして、必ずAとBの入れ替えになるということは、Aの移動回数だけ数えればそれが交換回数である。
これは「出発位置-目標位置」の絶対値の総和で簡単。

問題は目標地点の決め方だが、実は完成形は"ABAB..."か"BABA..."の2通りしかない。
よって、2パターンとも試して小さい方を答えればよい。

解答例

解答例

注意点

2つのどちらが正しい完成形なのかの判断は難しい

例えばABBBBAAAABという文字列の場合、元々最初がAで最後がBなのに、"BABA..."型の方が交換回数が少ない。
このように、完成形がどちらになるのか判別するのはなかなか難しい。
たかだか2通りなので、さっさと両方試してしまうのが正解。

答えがint型に入らない場合がある

Aを大量に並べた後Bを大量に並べられた場合に、答えが2*10^9を超える場合がある。
long long型を使うこと。

別解

deque※を使って、実際の構成を高速に行う

sの中身をdequeで管理し、今は不要な文字をdequeに管理しながら目的文字列を作ってもよい。
文字が2種類しかないため、今は不要な文字には絶対に1種類しか入らない。
よって、毎回「今は不要な文字の先頭を確認し、目的の文字じゃなかったら本体を探しに行く」という方針で実際の構成手順を高速に行うことができる。
解答例