きろく

特筆すべき記録のまとめ

AtCoder Beginner Contest 104 : D - We Love ABC

問題

D - We Love ABC

A,B,C,? で構成される文字列 S が与えられる.? は A,B,C のどれにも変化できる.このとき,S の中から3つ文字を選び,この選んだ文字を並べると ABC になる選び方の通り数を求める問題.|S| <= 10^5.

解法

SugarDragon5 ガチプロに解説して頂きました(ありがとうございました).

 考えられる全ての文字列の i 文字目までで A が合計いくつ出てくるかを S の最初から DP 的に考えていく.同様に,後ろから C についても計算し,ABC の真ん中 B か ? のところを中心にして左右に A,C がある個数を掛け合わせればよい.O(|S|).

解答

Submission #2997802 - AtCoder Beginner Contest 104

f:id:babcs2035:20180812193125p:plain

gist.github.com