AOJ-2340 : Carpenters' Language

Carpenters' Language

以下のような構文規則の言語がある

S -> SS | (S) | )S( | ε

空文字列Sに、Pの位置からCの文字をN個挿入する。出来た構文が規則通りか判定せよ。

この言語は ' ( ' , ' ) ' の数が等しいか判定するだけで解けます。 なので、それぞれの括弧の数を数え、等しいか判定するだけです。

しかし、この問題は、実際に入力を元に文字列を作ってその文字列を判定するというやり方ではTLEになるため解けません。テストデータに量が多い入力がたくさんあるために、素直に文字列を作っていると制限時間内に解けなくなります。

なので、入力から直接括弧の数を数えるだけでいいので実装は簡単になりますが、括弧の数を数える変数はint型ではオーバーしてしまうため、long long型でないといけません。それに気づければすぐに終わる問題です。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2340

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

int main()
{
	int Q;
	cin >> Q;

	int P,N;
	char C;
	long long LPAR=0, RPAR=0;
	rep(nth,Q)
	{
		cin >> P >> C >> N;
		
		if(C == '('){
			LPAR += N;
		}else{
			RPAR += N;
		}

		cout << ( (LPAR == RPAR) ? "Yes" : "No" ) << endl;
	}
	return 0;
}