AOJ 2369 CatChecker (JAG 冬合宿 2010 day3-A) (300 点)

カッコ列の整合性判定問題の亜種と言える。

• 問題へのリンク

問題概要

文字列 が cat 文字列であるとは、次の条件を満たすことをいう。

• は空文字列である
• ある cat 文字列 が存在して、 と表せる

与えられた文字列 が cat 文字列であるかどうかを判定せよ。

制約

• 

考えたこと

やるべきことは完全に「カッコ列整合性判定問題」と一緒。stack を用意して文字列 の文字を順に見ていき、

• "w" 以外が来たとき：stack に push
• "w" が来たとき：stack の末尾に対して、 "e" → "m" の順に pop する。そのように pop できなれれば "No"
• ただし途中で stack が空になったら "No" (mewmew はダメ)

計算量は となる。

コード

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

int main() {
    string S;
    cin >> S;
    
    auto solve = [&]() -> bool {
        vector<char> st;
        for (int i = 0; i < S.size(); ++i) {
            char c = S[i];
            if (c != 'w') st.push_back(c);
            else {
                if (st.empty() || st.back() != 'e') return false;
                st.pop_back();
                if (st.empty() || st.back() != 'm') return false;
                st.pop_back();
            }
            if (i != S.size()-1 && st.empty()) return false;
        }
        return st.empty();
    };
    cout << (solve() ? "Cat" : "Rabbit") << endl;
}