Official

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


R がやってくるごとに \(T\) を反転させると、最悪計算量が \(\Theta(|S|^2)\) となるため、 TLE してしまいます。
そこで、\(T\) を反転させる代わりに、現在反転しているかの変数を持ち、反転中は末尾への追加を先頭への追加と読み替えることにします。
先頭・末尾への文字の追加は deque というデータ構造を用いると高速に処理できます。

連続する同じ \(2\) 文字を削除する部分は、同じ \(2\) 文字が連続するとき、文字を追加する代わりに削除することで高速に処理できます。

回答例 (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;
}

回答例 (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: