読者です 読者をやめる 読者になる 読者になる

Minimum number of steps | Codeforces #411 (Div. 1)

abのような形が残らないので、操作していくと最終的に

bbb....baa...a

のような形になる。

とりあえず実験してみる。

ab

→bba

bはaを飛び越えるときに1個から2個になった。

abに対する操作は1回。

aab

→a<ab>

abba

→<ab>ba

→bbaba

→bb<ab>a

→bbbbaa

aを2個飛び越えることでbは4個になった。

abに対する操作は1+2回。

...

k>=1のとき

(aがk個)b→(bが2^k個)(aがk個)

abに対する操作は1+2+...+2^(k-1) 回

 

あとは、すべてのbについて、そのbより左にあるaを数えて、この操作回数の和を求めればいい。