Codeforces Round #431 (Div. 2) C. From Y to Y

問題ページ
codeforces.com

考えたこと

構成ゲーっぽい。適当な文字列についてcostがどのように求められるのか考えてみる。
まず、異なる文字種が影響し合うことはなさそう。ある文字種がN個存在するときについて考えると、costはN(N-1)/2になりそう。いくら実験しても操作の順番がcostに影響することはなかったので操作の順番は関係ないと思い込む。
A[i] = i*(i-1)/2 を前計算しておき、k以下の一番大きいA[i]を貪欲に取っていくとしてみる。k=100000付近のを試してみるが文字列長は問題なさそう。logオーダーで減っていくのでは？と思いこむ。
制約を見直したらk=0が含まれている。慌てて対処して投げたら通った。

学び

貪欲に取っていくパートでkはルートのオーダーで減っていくとTLで見た。k以下の最も大きいA[i]はkのルートオーダーになるのはそれはそうっぽい。26回ルートを取るならまず問題なさそう。