この問題は考察を問います。

問題の処理を愚直に実装していては、あるケースによっては計 O(S2)O(|S|^2) ※かかってしまい、時間制限に間に合いません。
これは文字列の反転に対して大方 O(S)O(|S|) を要するためです。では、どうすればよいでしょうか?

まず、SS に含まれる @ の個数が 11 個だけであったことを考えてみます。このときの添え字を ii とおきます。
問題文中にある「末尾までの連続部分文字列を反転する」ことは、言い換えれば「調べる添え字を反転させる」ことに相当します。

つまり SiSi+1SSS_iS_{i+1}\dots S_{|S|} を反転すると、SSSS1SiS_{\bm {|S|}}S_{\bm {|S|-1}}\dots S_{\bm i} となりますが、ちょうど iiS|S| の位置に来ていることがわかります。

さらに反転した文字列 SSSS1SiS_{{|S|}}S_{{|S|-1}}\dots S_{i} の中に @11 つ含まれていたとします。このときの添え字を jj とおきます。
この場合でも同じように、添え字を反転する方法を適用することができます。

例えば j=S1j=|S|-1 の場合、反転させる文字列は反転後の文字列 SS'i+1i+1 文字目※2から jj 文字目までです。
便宜上、SSSj=S1SiS_{{|S|}}S_{\bm{j}={|S|-1}}\dots S_{i} として見て( jj 文字目から末尾までの連続部分文字列を)反転させると、SSSiSi+1Sj=S1S_{{|S|}}S_{\bm i}S_{\bm{i+1}}\dots S_{\bm{j=|S|-1}} となり、確かに添え字が反転していることがわかります。
これは @22 個以上含まれている場合も同様に適用できます。

以上の考察から、「現時点で処理されていない @ の中で一番最初に登場する場所(添え字 ii とします)から、末尾までの連続部分文字列を反転する」処理は、次のように行うことで全体で O(S)O(|S|) で行うことが可能です。

  • 先頭の添え字 f(=1)f(=1) 、末尾の添え字 b(=S)b(=|S|) として、現在調べている文字が @ であったとき、
    • 現在調べた文字を含む @ の個数が偶数個であったら、調べる添え字を bb として、b=S,S1,S2,,fb=|S|,|S|-1,|S|-2,\dots,f の順で次に登場する @ を探索する
    • 現在調べた文字を含む @ の個数が奇数個であったら、調べる添え字を ff として、f=b,b+1,b+2,,Sf=b,b+1,b+2,\dots,|S| の順で次に登場する @ を探索する

この場合の処理の終了条件は f=bf=b であることです。これはこの条件を満たしたら、次に調べる文字が存在しないことを意味します。
したがってこの問題を O(S)O(|S|) で解くことができました。

解答例(C++):


例えば SS@ と英小文字 11 文字だけで構成されている場合などは、全体の処理を 1+2++(S1)=12S(S+1)1+2+\dots+(|S|-1)=\cfrac{1}{2}|S|(|S|+1) 回行わなければなりません。

※2
反転した後は、「調べる添え字」だけが反転することに注意してください。全体として見ると、反転する対象の文字の添え字は変化しません。

例えば S=S= ab@cd@ek を考えてみます。最初に 33 文字目(「調べる添え字」に相当)を処理しますが、11 回目の処理後の文字列は abke@dc となります。
11 回目の処理は 4\bm 4 文字目から末尾まで、22 回目は 6\bm 6 文字目から末尾までとなり、反転する対象の文字列の添え字は単調増加です。
対して「調べる添え字」は、11 回目の処理は f=3f=3 から l=8l=8 に移り、22 回目の処理は l=8,7,6l=8,7,6 の順で探索し l=6l=6(文字列の添え字 55 文字目に相当)から f=3+1=4f=3+1=4 に移ります。
ここでの +1+1 という操作は @ を答えとなる文字列に含めないようにしています。