めちゃくちゃ面白かった！

問題概要

$N$ 個のカッコ列 $S_{1}, \dots, S_{N}$ が与えられる。これらを並び替えて連結して 1 個の文字列を作る。

この文字列が「整合のとれたカッコ列」となるようにすることが可能かどうかを判定せよ。

制約

$1 \le N \le 100$
$1 \le |S_{i}| \le 100$

考えたこと

大前提として、文字列 $T$ が「整合のとれたカッコ列」であるための必要十分条件は次のようになる。初期状態を 0 とした変数 cur を用意して、文字列 $T$ を左から順番に見ていって、

'(' では ++cur
')' では --cur

をしたときに、

一度も cur < 0 とはならない
最終状態で cur = 0 となる

ことが必要十分である。これを踏まえて、各カッコ列を次の 2 つの値で特徴付けることにした。

need：その文字列を連結する前段階で、cur >= need でなければならない
- たとえば "))))(" では、need = 4
diff：その文字列によって cur の値がどのように変化するか
- たとえば "))))(" では、diff = -3

そもそも diff の総和が 0 でない場合は明らかにダメなので、以降 diff の総和は 0 であるとする。さて、カッコ列全体は次の 3 パターンに分類できる。

need = 0, diff >= 0 であるもの
need > 0, diff >= 0 であるもの
need > 0, diff < 0 であるもの

まずパターン 1 は無条件に使うことができて、なおかつ先に使うことで後が楽になるものなので、最初に全部連結することにする。

次に、仮にパターン 3 のあとにパターン 2 を使うことで可能な並び替えが存在すると仮定すると、それは swap しても可能であることに注意する。よって、パターン 2 を上手に並べて連結するのをすべて終えたあとで、パターン 3 を上手に並べて連結していくものとしてよい。

パターン 2

パターン 2 については、need の小さい順に並べていけば良さそうである。

(need 大) → (need 小)

の順序で可能なものがあったとき、これをひっくり返しても可能だからだ (diff >= 0 より、cur が広義単調増加であることに注意)。

パターン 3

パターン 3 については、

diff の絶対値が小さいもの (diff が大きいもの) から使いたい
need が小さいものから使いたい

という複数の要求があって難しい。しかし、(need, diff) が

(m, -a) → (n, -b)　(m - a < n - b とする)

の順序で可能であったとき、これをひっくり返しても可能であることを示すことができる。よって、「need + diff」が大きい順に並び替えれば OK。

まとめ

以上をまとめて、カッコ列を並び替えて、最後に整合性を check すれば OK。計算量は $O(|S_{i}| N \log N)$ となる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pll = pair<long long, long long>; // need, diff
pll calc(const string &S) {
    int cur = 0, need = 0;
    for (auto c : S) {
        if (c == '(') ++cur;
        else --cur;
        chmax(need, -cur);
    }
    return pll(need, cur);
}

int main() {
    int N;
    cin >> N;
    long long cur = 0;
    vector<pll> plus, minus;
    for (int i = 0; i < N; ++i) {
        string S;
        cin >> S;
        pll p = calc(S);
        if (p.first == 0) cur += p.second;
        else if (p.second >= 0) plus.push_back(p);
        else minus.push_back(p);
    }
    sort(plus.begin(), plus.end());
    sort(minus.begin(), minus.end(), [&](pll x, pll y) {
        return x.first + x.second > y.first + y.second;
    });
    bool res = true;
    for (auto p : plus) {
        if (cur < p.first) res = false;
        cur += p.second;
    }
    for (auto p : minus) {
        if (cur < p.first) res = false;
        cur += p.second;
    }
    if (res && cur == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}