AOJ 2340: Carpenters' Language

はじめに

• 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2340
• Javaで実装

問題文概訳

International Carpenters Professionals Company (ICPC) は 大工のエキスパートを集めた会社です。 ICPCは独自の言語を開発しました。

この言語を文脈自由文法で表すと以下の通りである。

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

アレックスはICPCの言語を学ぼうとした、 まずは、ある文字列がこの言語にそっているかどうかを確認しようとした。 そこで、偉大なるプログラマのあなたに、それを判定するプログラムを書いて欲しいとお願いしてきた。

アレックスの要求は次のとおりである。 まず最初に、空の文字列が与えられる。 そして、'('または')'からなる文字列をそこに追加していくことで、 文字列を生成していく。 あなたはq個のクエリを与えられる。 それぞれのクエリは、(p, c, n)　からなる。 pは挿入位置、cは'('または')'のいずれか、nはcをいくつ挿入するかを表す。 それぞれのクエリが与えられた後、Sが言語にそっているなら "Yes"、 そうでなければ "No" を出力せよ。

アレックスの勉強を助けるために、そして彼の落第を阻止するためにも。

1 <= q <= 10⁵, 1 <= i <= q, 0 <= p <= Sの長さ, 1 <= n <= 2²⁰

解法

文脈自由文法を見て考えると、実は(と)の数が同じであればこの言語に合致するということになる。なので実は何処に挿入するか関係なく、数だけ数えれば良い。

2²⁰ ≒ 10⁶ で、q <= 10⁵ なので、(と)の数は最大で10¹¹ となる。10⁹を超えるとintには収まらないので、longを使わなければならない点にだけ注意が必要である。

ソースコード

• http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1371919

class Main {
    public static void main(String[] args) throws Exception{
        
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(br.readLine());
        
        long[] cnt = new long[2];
        
        for (int i = 0; i < m; i++) {
            String[] in = br.readLine().split(" ");
            int c = (int)(in[1].charAt(0) - '(');
            int n = Integer.parseInt(in[2]);
            cnt[c] += n;
            if(cnt[0] == cnt[1]){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }
        }
    }
}