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: