Hello 2019 C. Yuhao and a Parenthesis

codeforces.com

問題文（意訳）

こんな問題

このように括弧が書かれた組がいくつかあります。これらのうち、いくつかを組み合わせて正しい組み合わせにすると、何組できるでしょうか。（正しい組み合わせとは、組み合わせたものの括弧がきちんとしている(?)こと）

ポイント

• 英語が読めない
• 括弧が成り立っているかの判定
• 気をつけないとTLEするので計算速度は大切
• 与えられる括弧の組が正しいとは限らない「))(()」

全体的な解法

1. 全ての括弧のかたまりを括弧レベル(造語)ごとにグループ分けしてカウントしておく
( = 1, ()( = 1, ))() = -2, ()() = 0, (())((()() = 2, ))))) = -5

2. それの逆(2なら-2)が既に手持ちにあればそれと合体させて括弧は成り立つので、ans++; していく。酸性のやつと塩基性のやつを混ぜて中和するイメージ。
「括弧レベル4のかたまりは括弧レベル-4のかたまりと合体すると成り立つ」

3. ansを出力する

括弧のかたまりを区別する

揃っている括弧はキャンセルというか無視できます。

左から順にスタックに詰めていって、元のtopが'('で今から入れるのが')'のとき、キャンセルして消せます。これを最後まで続けるとシンプルな形になります。詰めていく時に')'だとcount++して、'('だとcount--とすると、終わった時にcountが括弧レベル(造語)になっているので便利です。

シンプルにした時、左端が')'で右端が'('の場合、どうにもならないので見捨てます。さようなら。ちなみに左端を見るために自分はスタックではなくdecueを使いました。

map<括弧レベル,いくつあるか> みたいなmapを0で初期化して作っておいて、その括弧レベルの値を++してあげればいいです。
もし、その前に既にその括弧レベルの逆が手持ちにあれば、括弧レベル(逆)から1を引いてansに1足せばいいです。

一応ですが自分のコードです

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main() {
  int n;
  cin >> n;
  vector<int> v(n);
  map<int, int> m;
  ll ans = 0;

  for (int i = 0; i < n; i++) {
    string s;
    cin >> s;
    deque<int> bra;
    int count = 0;

    for (int j = 0; j < s.size(); j++) {
      if (!bra.empty() && bra.back() == '(' && s[j] == ')')
        bra.pop_back();
      else
        bra.push_back(s[j]);

      if (s[j] == '(')
        count++;
      else
        count--;
    }

    if (!(bra.front() == ')' && bra.back() == '(')) {
      if (m[count * -1]) {
        m[count * -1]--;
        ans++;
      } else {
        m[count]++;
      }
    }
  }
  cout << ans << endl;
}

以上です。何かあったらコメントしてくれると嬉しいです。もっと簡単な方法がありそう。