ちきんの括弧並べ [yukicoder No.790] - はまやんはまやんはまやん

解説

https://yukicoder.me/submissions/319026

考えうる文字列を全探索しよう。
これは、bitを使った全探索で行う。
以下では、1を'('、0を')'として実装している。
正しいカッコ列かの判定は(なら+1, )なら-1とする典型手法があり、
これで「途中で負にならない」「最後は0」を満たすなら、正しいカッコ列となる。
　
注意点として、bit全探索をするが、判定部分でO(N)かかるので、普通にやると
O(2^(2N)*2N)となりTLEする。
判定したいのは、1がN個立っているものだけなので、__builtin_popcountで1が立っているのがN個のものだけ判定するようにすれば、O(2^(2N)+C(2N,N)*N)となり、通る。

void _main() {
    cin >> N;

    int ans = 0;
    rep(msk, 0, 1 << (N * 2)) if(__builtin_popcount(msk) == N) {
        int cnt = 0, ok = 1;
        rep(i, 0, N * 2) {
            if (msk & (1 << i)) cnt++;
            else cnt--;

            if (cnt < 0) ok = 0;
        }
        if (ok) ans++;
    }
    cout << ans << endl;
}