AGC055 A - ABC Identity (400)
コンテスト中の考察
ABCの並び替えが6種類なのでこれで網羅できそう
愚直解でも6種類でできるか試す方法は$ \mathcal{O}(6^N)しか思い浮かばなかった
解説の解法
文字列を前からn文字ずつの3つに分ける
以下を順に行う
3つの文字列から順に未選択のABCの数を計算して一番少ない数でこの文字列に使うことを決定
3つの文字列から順に未選択のACBの数を計算して一番少ない数でこの文字列に使うことを決定
3つの文字列から順に未選択のBACの数を計算して一番少ない数でこの文字列に使うことを決定
3つの文字列から順に未選択のBCAの数を計算して一番少ない数でこの文字列に使うことを決定
3つの文字列から順に未選択のCABの数を計算して一番少ない数でこの文字列に使うことを決定
3つの文字列から順に未選択のCBAの数を計算して一番少ない数でこの文字列に使うことを決定
各文字列に含まれる文字の数を適当において計算すると、5個の文字列に分けきることができるのが分かる
各文字に割り振っていくだけなので$ \mathcal{O}(N)