Official

D - 宇宙人からのメッセージ / Message from Aliens Editorial by en_translator


If we reverse \(T\) for every occurrence of R, the worst time complexity will be \(\Theta(|S|^2)\), which leads to TLE.
Instead of reversing \(T\) every time, we can store a variable of whether \(T\) is reversed or not, and regard the operation of appending back as that of appending front while reversed.
Appending a character to the front or to the back can be processed fast with a data structure called deque.

Also, when we encountered two consecutive same characters, rather than removing them after all the operations have ended, we can remove the former instantly instead of appending the latter, in order to avoid bad performance.

Sample Code (C++)

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

int main(){
    string S;
    cin >> S;
    deque<char> q;
    bool rev = false;
    for(char c : S){
        if(c == 'R') rev ^= 1;
        else if(rev) q.push_front(c);
        else q.push_back(c);
    }
    if(rev) reverse(q.begin(), q.end());
    string T;
    for(char c : q){
        if(T.size() && T.back() == c) T.pop_back();
        else T.push_back(c);
    }
    cout << T << endl;
}

Sample Code (Python)

from collections import deque
s = deque()
rev = False
for i in input():
    if i == 'R':
        rev = not rev
    elif rev:
        if s and s[0] == i:
            s.popleft()
        else:
            s.appendleft(i)
    else:
        if s and s[-1] == i:
            s.pop()
        else:
            s.append(i)
if rev:
    s = reversed(s)
print("".join(s))

posted:
last update: