Wrong Brackets [CSAcademy #51 E]

https://csacademy.com/contest/round-51/task/wrong-brackets/

問題概要

2*N文字で'('がN文字で')'がN文字の括弧列のうち、辞書順でK番目に正しくない括弧列を求めよ。
N≦30

解法

先頭から順番に決めていく手法を使う。
もし'('を置いた時にその後作れる正しくない文字列の個数がK以上となれば、'('を置ける。
　
その為にf(sm,L,R)関数を用意する
f(sm,L,R) := 今までに置いた括弧列で"("の数が")"よりもsm個多く、"("がL個、")"がR個まだ置けるときに正しい括弧列は何通り作れるか
これはf(sm+1,L-1,R)+f(sm-1,L,R-1)で求めることができる（"("を置くか")"を置くかの2つの遷移）。
状態数はそんなに無いので、メモ化をすればこの関数の計算量は大丈夫。
　
これから"("をL個、")"をR個使えるとすると、その後作れる正しくない文字列の個数はC(L+R,L) - f(sm,L,R)となる。
桁DPの復元をやるような感じで番目を超えないように上手くやっていけば正しくない括弧列を求められる。

typedef long long ll;
#define CMAX 101
int noinit = 1; ll memo[CMAX][CMAX];
ll aCb(ll a, ll b) {
    if (noinit) {
        rep(i, 0, CMAX) rep(j, 0, CMAX) memo[i][j] = -1;
        noinit = 0;
    }
    if (b == 0 || a == b) return 1;
    if (0 <= memo[a][b]) return memo[a][b];
    return memo[a][b] = aCb(a - 1, b - 1) + aCb(a - 1, b);
}


int N; ll K;
//---------------------------------------------------------------------------------------------------
ll dp[101][101][101];
int vis[101][101][101];
ll f(int sm, int L, int R) {
    if (sm < 0) return 0;
    if (vis[sm][L][R]) return dp[sm][L][R];

    if (L == 0 && R == 0) {
        if (sm == 0) return 1;
        else return 0;
    }

    ll res = 0;
    if (L) res += f(sm + 1, L - 1, R);
    if (R) res += f(sm - 1, L, R - 1);

    vis[sm][L][R] = 1;
    dp[sm][L][R] = res;

    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;

    string ans = "";
    int cnt = 0, L = N, R = N;
    ll top = 1;
    rep(i, 0, N * 2) {
        if (R == 0) {
            ans += "(";
            L--;
            cnt++;
            continue;
        }

        ll d = 0;
        if (L) {
            d = aCb(L - 1 + R, L - 1) - f(cnt + 1, L - 1, R);
            //printf("%d %lld\n", i, d);
            if (K < top + d) {
                ans += "(";
                L--;
                cnt++;
                continue;
            }
        }

        R--;
        ans += ")";
        cnt--;
        if (cnt < 0) cnt = -1010;
        top += d;
    }

    printf("%s\n", ans.c_str());
}