editorialと違う気がしたので記事2個目
厳密じゃないです、ごめん(書けないので)
※全く証明にはなってないです。
代わりにまともに示してくれる or 反例をくれる人歓迎しています。
問題概要
a,b,cが全て存在する場合、f(T)はaで始まるので、もともとaだけの文字列があり、aとaの間にbまたはcをだいたい同じ個数ずつ挿入していきたい気持ちになります。
また、abcというsubstringの代わりに、acbというsubstringを作ってもf(T)が小さくなることはないことがわかります。
この考察をベースに考えます。
A%BでAをBで割ったあまりを表すこととします。
入力の和をNとします。
① 文字が1種類のとき
自明
② 文字が2種類のとき
aがA個、bがB個、cが0個とした問題が解ければ、a,b,cのどれが0個のときでも同様に解くことができる。
BがAの倍数のとき
(aを1個)+(bをB/A個)+(aを1個)+(bをB/A個)+...とするのが最適である。
BがAの倍数でないとき
(aを1個)+(bをfloor(B/A)個) という文字列xをA-(B%A)個 (=X個とする)
(aを1個)+(bをfloor(B/A)+1個) という文字列yをB%A個 (=Y個とする) 作り、
a->x, b->y, A->X, B->Yに置き換えて②を解いたものが最適である。
A+B>A=X+Yより、常にA+Bが減少していくので最大でもN回②を解けば終わることはわかる。(実際はgcdっぽいからlog？)
③文字が3種類のとき
aがA個、bがB個、cがC個とした問題を解くことを考える。
CがAの倍数のとき
(aを1個)+(cをC/A個)という文字列xをA個作り、
a->x, b->b, A->A, B->Bに置き換えて②を解いたものが最適である。
これは、abcよりacbの順のほうがf(T)が大きくなることと関係している。
以下、CがAの倍数でない時を考える。
Z=C%A, rem=A-Zとする。
Bがremの倍数のとき
(aを1個)+(cをfloor(C/A)個)+(bをB/rem個)という文字列yをrem個
(aを1個)+(cをfloor(C/A)+1個) という文字列zをZ個 作り、
a->y, b->z, A->rem, B->Zに置き換えて②を解いたものが最適である。
これは、cをほぼ同数ずつaの直後に入れたくて、cが少ない方(floor(C/A)個の方)が辞書順では弱いのでそっちをbでできるだけ強化したいという感じ。
BがAの倍数でないとき
X=rem-(B%rem), Y=B%remとする。
(aを1個)+(cをfloor(C/A)個)+(bをfloor(B/rem)個)という文字列xをX個
(aを1個)+(cをfloor(C/A)個)+(bをfloor(B/rem)+1個)という文字列yをY個
(aを1個)+(cをfloor(C/A)+1個) という文字列zをZ個 作り、
a->x, b->y, c->z, A->X, B->Y, C->Zに置き換えて③を解いたものが最適である。
A+B+C>A=X+Y+Zより、常にA+B+Cが減少していくので最大でもN回③を解けば終わることはわかる。
ACコード
まあACしたのでたぶんあってます
まとめ
解説記事を書いてる人を尊敬します
