問題の概要
ある文字列Sに対してQ回のクエリが投げられる．各クエリの内容は以下の通りである．
- 文字列Sの反転
- 文字列Sの先頭/末尾への文字Ciの追加
問題自体はシンプルであり，Q回のクエリにそれぞれ従えばいいと考えられる．が，愚直に繰り返すとreverse()とクエリを回すループとで計算量がマズイことになる．この計算量の削減がこの問題で問われる工夫点（だと思う）．
私のアプローチ
元の文字列Sと追加される文字Ciを分解して考える．元の文字列Sの操作（A）後，追加文字Ciの操作（B）を行う．
元の文字列Sの操作（A）
文字列の反転クエリの回数の偶奇で最終的な文字列Sの反転が決定する．奇数回ならば与えられた文字列は反転する．
追加される文字Ciの操作（B）
文字追加の箇所（先頭/末尾），追加してからの反転操作回数の偶奇によって最終的な文字列Sでの配置が決定する．
- クエリが先頭に追加 かつ 偶数回の反転操作 ならば 文字Ciは文字列Sの先頭に配置
- クエリが先頭に追加 かつ 奇数回の反転操作 ならば 文字Ciは文字列Sの末尾に配置
- クエリが末尾に追加 かつ 偶数回の反転操作 ならば 文字Ciは文字列Sの末尾に配置
- クエリが末尾に追加 かつ 奇数回の反転操作 ならば 文字Ciは文字列Sの先頭に配置
これをクエリの順に操作（A）が適用された文字列Sに対して適用する．
課題となった点と解決
愚直に以上のアプローチを実装したのが以下の提出である．2104msもかかっている．
atcoder.jp
コンテスト中では不明だったが，私のアプローチのボトルネックとなった箇所は解答によるとStringの先頭への文字追加である．この解答の記述によると，dequeを使うといいらしい．これを使用した提出が以下である．
atcoder.jp
181msまで短縮した．スゴい．
まとめと感想
コンテスト中では勝手にstringのメンバ関数の計算量がわずかに悪いのではなど考えていたが，単純な式文に潜む落とし穴を経験することができたのが今回の大きな収穫だ．stringの先頭への文字操作は悪い．代わりにdequeを使おう．
