Japan Alumni Group Summer Camp 2015 Day 2
日本語
日本語
English
新規登録
ログイン
C - ABC Gene 解説
by
snuke
考察
文字 x を置換すると、置換後の文字列に現れる x の個数は A, B, C の中で最小になる
置換後の文字列に現れる “ABC” は全て置換で追加されたものである
解法
「S に現れる “ABC” を全て、頻度最小の文字に置換する」を繰り返す
ステップ数は高々
\(|S|\)
回なので
\(O(|S|^2)\)