ABC200-D

D - Message from Aliens

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    string s;
    cin >> s;
    deque<char> dq;
    ll n = s.size();
    ll flag = 1;
    for(ll i=0; i<n; i++){
        if(s[i] == 'R'){
            flag*=-1;
        }else{
            if(flag == 1){
                if(!dq.empty() && s[i] == dq.back()) dq.pop_back();
                else dq.push_back(s[i]);
            }else{
                if(!dq.empty() && s[i] == dq.front()) dq.pop_front();
                else dq.push_front(s[i]);
            }
        }
    }
    string T = "";
    for(char x : dq) T+=x;
    if(flag == -1) reverse(T.begin(), T.end());
    cout << T << endl;

    return 0;
}

感想

先頭要素や末尾の要素を削除するために、sutstrやdeleteを使うとo(n)くらいかかるため、時間が間に合わない。デキューは、末尾先頭への要素の追加削除,参照をo(1)で行うため、この問題を解くことに適している。それから、デキューが空の状態で中身を参照すると、配列外参照となるため、以下のようにして対応する。!dq.empy()が偽の時それ以降のs[i] == dq.back()が行われない。逆に左右を逆にすると最初に、dq.back()の参照が行われてしまい、配列外参照のエラーになる恐れがあるため、必ず左側に!dq.empty()を書く必要がある。

 if(!dq.empty() && s[i] == dq.back()) dq.pop_back();