AtCoder ABC 283 D - Scope (3Q, 茶色, 400 点)

スタックによるシミュレーション問題！

• 問題へのリンク

問題概要

整合のとれたカッコ列に対して、英小文字がいくつか挿入されてできる文字列が与えられる (たとえば、"(a(ba))c")。

このような文字列に対して、高橋君が気絶するかどうかを判定したい。次のように判定する。最初、空の箱を用意して、文字列の文字を左から順にみていき、次の処理を実行する。

• 英小文字の場合：もしその文字がすでに箱に入っていたら高橋君は気絶する。そうでなかったら、その文字を箱に入れる
• '(' の場合：何もしない
• ')' の場合：それに対応する '(' との間に挟まれた文字をすべて箱から除去する

高橋君が気絶するかどうかを判定せよ。

制約

• 

考えたこと

もし「気絶」がなかったら、よくある「stack のシミュレーション」だ。stack のシミュレーションに馴染みがなかったら、次の問題集の最初の方の問題をぜひ解こう！

atcoder-novisteps.vercel.app

ここでは、stack のシミュレーションに馴染みがあることを前提とする。その場合、この問題特有の事情は

---

• 箱に文字を入れる
• 箱に文字が入っているかどうかを判定する

---

という部分に尽きる。この処理は、バケットや set を用いて効率よく判定できる。

全体として、計算量は となる。

コード

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

int main() {
    string S;
    cin >> S;
    vector<bool> isin_stack(26, false);  // 各文字がスタックに入っているかどうか
    vector<char> st;  // スタック
    for (auto c : S) {
        if (c == ')') {
            while (!st.empty() && st.back() != '(') {
                isin_stack[st.back() - 'a'] = false;
                st.pop_back();
            }
            st.pop_back();  // '(' まで除去する
        } else if (c == '(') {
            st.push_back(c);
        } else {
            if (isin_stack[c - 'a']) {
                // 文字 c がすでにスタックに入っていたら気絶する
                cout << "No" << endl;
                return 0;
            }
            st.push_back(c);
            isin_stack[c - 'a'] = true;
        }
    }
    cout << "Yes" << endl;
}