読者です 読者をやめる 読者になる 読者になる

JAG Contest 2016 Domestic A - 阿吽の呼吸

ICPC系

jag2016-domestic.contest.atcoder.jp

問題文

省略

解法(反転して表示)

本質的には括弧列が与えられるのでvalidな括弧列ですかという問題に言い換えれば見通し良く解ける. カウンタを定義する.「A」が来たらカウンタをインクリメント,「Un」が来たらデクリメント,途中でカウンタが負の数になったらNO,最後まで処理してカウント!=0ならNO.

ソース

#include <bits/stdc++.h>
using namespace std;
 
int main(){
    int a = 0;
    int n;
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        string t;
        cin >> t;
        if( t == "A" ){
            a++;
        }else{
            a--;
            if( a < 0 ){
                cout << "NO" << endl;
                return 0;
            }
        }
    }
    if( a == 0 ) cout << "YES" << endl;
    else cout << "NO" << endl;
}