ABC 401-500/ABC447D - Take ABC 2 - 競技プログラミング用 知識集積所

---

問題

ABC447D

必要知識

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

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

考え方

仮にN回操作を行うとして、以下のような貪欲法※が成立する。

まず、Aの選び方は、登場位置が速い方からN個を採用すればよい。
というのも、i番目のAが不採用でj番目のAが採用(i<j)となっている場合、j番目の代わりにi番目を使うことが必ずできるため。

次に、Bの選び方は、各Aの出現位置より後ろでなるべく登場位置が速いものを重複なく採用すればよい。
理由はAの場合と同様。

最後に、Cの選び方は、各Bの出現位置より後ろでなるべく登場位置が速いものを重複なく採用すればよい。
理由も同様。

つまり、結局のところ、

• 文字列の中で最初に登場するAを探していく
• Aを見つけたら、そこから後ろで最初に登場するBを探す
• Bを見つけたら、そこから後ろに最初に登場するCを探す
• その3つを取り除く文字に決める

を繰り返すことで解答を得る。

ただし、これをそのまま実装するとTLEする。
AとBとCそれぞれの出現位置をvectorかdeque※あたりに全部入れておき、それら3本のデータを前から見ながら探索するとよい。

解答例

解答例

注意点

別解