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

土下座しながら探索中

主に競技プログラミング

AOJ 2340 : Carpenters' Language

問題リンク:Carpenters' Language | Aizu Online Judge

問題概要:
S -> SS | (S) | )S( | ε 
このような文法の言語があり、入力がその言語になっているなどうが判定せよ

使用した言語:C++

解法:
'('と')'の数が等しい場合は全て正しい文法なので'('と')'の数を数え,両方の数がひとしいなら"Yes",異なるなら"No"と出力すればよい
ここで注意すべき点は、'('と')'の数を数える際にはlong longを使わなければならないこと
クエリーが10^5で'('と')'の数は最大2^20なのでintには収まらない

コード:

#include<iostream>
 
using namespace std;
 
int main()
{
  int n;
  cin >> n;
  long long cnt = 0;
  for(int i=0;i<n;i++)
    {
      int a,b; char c;
      cin >> a >> c >> b;
      c == '('?cnt += b:cnt -= b;
      !cnt?cout << "Yes" << endl:cout << "No" << endl;
    }
  
  return 0;
}