Codeforces Round #200 (Div. 1) B. Alternating Current

この問題面白かったです。

問題

Codeforces

解法

同じ記号が連続していると, その部分は何もないのと同じにしても良いです。
例えば, -++- の記号を考えます。このとき, ++ の部分は + が - の上に乗っかっているだけなので -- という記号列と同じ意味になります。そして -- という記号列は 何も糸同士で絡まりがない "" (空文字) と同じ意味になります。よって, これは絡まってないので答えは "Yes" です。

上で述べたことを高速に計算するために, stack データ構造を使います。

int MAXN = 100010;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int n = s.size();
    stack<char> st;
    for (int i = 0; i < n; i++) {
        if (st.empty()) st.push(s[i]);
        else {
            if (st.top() == s[i]) st.pop();
            else st.push(s[i]);
        }
    }
    if (st.empty()) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}