ABC 158 D - String Formation

まだ道具としてのcppを使いこなせていないと感じた。

初手の方針

string ac,adにそれぞれ反転したものと反転していないもの両方を常に保持、stringの連結は+演算子で行う。

業務でプログラムしてるとstringの連結の計算量とか気にすることがなかったのでハマった。（ただよくよく考えたらjavaのStringBufferとかも同じ用途なので業務で計算量意識していなかっただけであった...）

stringの内部実装を見ていないので断言できないが、stringをchar[]と捉えると前方に要素を挿入することになるので確かに計算量多そうな印象はある。またac,adを転置させるためにaeに一時的に参照をもたせているがこれも良くなくてswapを使うとO(1)で済む。

変更点としてはstringは用いずdequeでac,aeを保持するようにしている。文字列のfront,backへの挿入もこれであれば計算量O(1)で済む。また転置についてはswapで行うとこれも計算量O(1)で済む。