きろく

特筆すべき記録のまとめ

AtCoder Grand Contest 034:B - ABC

問題

atcoder.jp

解法

"BC" という文字列は分断されたり "B" と "C" が独立して操作に影響を与えることはないので 1 つの文字に置き換えて考えてしまってよい."BC" を "X" と置き換えると,問題文中の操作は

s の連続した部分文字列であって "AX" であるようなものをひとつ選び,"XA" に書き換える

と言い換えることができる.そうすると,あとは各 "X" より左に連続する "A" の個数がその "X" が操作されうる最大の回数となるので,置き換えた後の文字列を左から "A" を数えたりしながら処理をすれば簡単に答えを求めることができる.O(|S|).

解答

atcoder.jp

"BC" を別の文字に置き換えてしまってよいことに気付いてしまえば,あとは自明な問題にすることができる.

f:id:babcs2035:20190605230216p:plain