この問題は考察を問います。
問題の処理を愚直に実装していては、あるケースによっては計 ※かかってしまい、時間制限に間に合いません。
これは文字列の反転に対して大方 を要するためです。では、どうすればよいでしょうか?
まず、 に含まれる @ の個数が 個だけであったことを考えてみます。このときの添え字を とおきます。
問題文中にある「末尾までの連続部分文字列を反転する」ことは、言い換えれば「調べる添え字を反転させる」ことに相当します。
つまり を反転すると、 となりますが、ちょうど が の位置に来ていることがわかります。
さらに反転した文字列 の中に @ が つ含まれていたとします。このときの添え字を とおきます。
この場合でも同じように、添え字を反転する方法を適用することができます。
例えば の場合、反転させる文字列は反転後の文字列 の 文字目※2から 文字目までです。
便宜上、 として見て( 文字目から末尾までの連続部分文字列を)反転させると、 となり、確かに添え字が反転していることがわかります。
これは @ が 個以上含まれている場合も同様に適用できます。
以上の考察から、「現時点で処理されていない @ の中で一番最初に登場する場所(添え字 とします)から、末尾までの連続部分文字列を反転する」処理は、次のように行うことで全体で で行うことが可能です。
@ であったとき、
@ の個数が偶数個であったら、調べる添え字を として、 の順で次に登場する @ を探索する@ の個数が奇数個であったら、調べる添え字を として、 の順で次に登場する @ を探索するこの場合の処理の終了条件は であることです。これはこの条件を満たしたら、次に調べる文字が存在しないことを意味します。
したがってこの問題を で解くことができました。
解答例(C++):
※
例えば が @ と英小文字 文字だけで構成されている場合などは、全体の処理を 回行わなければなりません。
※2
反転した後は、「調べる添え字」だけが反転することに注意してください。全体として見ると、反転する対象の文字の添え字は変化しません。
例えば ab@cd@ek を考えてみます。最初に 文字目(「調べる添え字」に相当)を処理しますが、 回目の処理後の文字列は abke@dc となります。
回目の処理は 文字目から末尾まで、 回目は 文字目から末尾までとなり、反転する対象の文字列の添え字は単調増加です。
対して「調べる添え字」は、 回目の処理は から に移り、 回目の処理は の順で探索し (文字列の添え字 文字目に相当)から に移ります。
ここでの という操作は @ を答えとなる文字列に含めないようにしています。