Message from Aliens [ZONeエナジー プログラミングコンテスト “HELLO SPACE” D]

https://atcoder.jp/contests/zone2021/tasks/zone2021_d

解説

https://atcoder.jp/contests/zone2021/submissions/22237589

実装問題であるが、一部実装を工夫しないとTLEする。

Tを反転させる

反転操作は時間がかかるので、文字列をなるべく反転させないようにする。
文字列が反転しているかを変数revで保持しておいて、反転されていれば文字列を末尾でなく、先頭に加えることにする。
このような場合、先頭からも末尾からも追加するようなデータ構造としてdequeを使おう。

同じ文字が2つ連続で並んでいたら取り除く

2つ連続で並んでいたら取り除く操作を1走査で1回だけ削除とすると、
abcdefghiihgfedcba
のような場合で、1回の走査で1組しか消せず、何回も文字列全体を走査することになる。
このような実装ではTLEするので、1組消したらその消した部分でもう一回消せないかというのを判定して、次々消していくようにする。
これもdequeを使って実装できる。
これまでの文字列をansというdequeで保持しておき、文字列を見ていく。
ansに文字が入っていて、かつ、末尾が今見ている文字列と同じなら消せるので、ansから末尾popする。
そうでないなら、ただ単にansの末尾にその文字を追加して次に行けばいい。
こうすることで末尾の比較と削除をしながら消す操作も終えることができる。

string S;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;

    deque<char> deq;
    bool rev = false;

    fore(c, S) {
        if (c == 'R') rev = !rev;
        else {
            if (rev) deq.push_front(c);
            else deq.push_back(c);
        }
    }

    if (rev) {
        deque<char> deq2;
        while (!deq.empty()) {
            deq2.push_back(deq.back());
            deq.pop_back();
        }
        deq = deq2;
    }

    deque<char> ans;
    while (!deq.empty()) {
        char c = deq.front();
        deq.pop_front();

        if (!ans.empty() && ans.back() == c) {
            ans.pop_back();
        }
        else {
            ans.push_back(c);
        }
    }

    string T = "";
    while (!ans.empty()) {
        T += ans.front();
        ans.pop_front();
    }
    cout << T << endl;
}