CS Academy Wrong Brackets

リンク : https://csacademy.com/contest/archive/task/wrong-brackets/statement/

問題概要

( がN個、) がN個の文字列で、括弧の対応が正しくない文字列の中で辞書順でK番目を求めよ。

解説

辞書順より前から求めることを考える。次に ( か ) のどっちを置くか考えるとき、
まだ正しい括弧列になりうる場合
次が ( のときの全通りより、次が ) の場合のほうが大きいため 次が ( であり、後ろが正しくない括弧列の通り数とKのどちらが大きいか毎回比べると最終的な括弧列が求められる。
すでに正しくないことが確定した場合
残っているときは後ろが正しい括弧列でもいいため、コンビネーションを使って次が ( であり、後ろが何でもよいときの通り数とKを比べる。
方針ミス+初期化ミスで地獄見た...

LL n, k, C[100][100],dp[100][100];
LL func(int p, int q) {
    if (dp[p][q] != -1)return dp[p][q];
    if (q == 0)return dp[p][q] = 1;
    if (p == 0)return dp[p][q] = 0;
    if (q < p)return 0;
    if (p == q)return dp[p][q] = C[p * 2][p - 1];
    return dp[p][q] = func(p - 1, q) + func(p, q - 1);
}

int main() {
    string str = "";
    cin >> n >> k;
    rep(i, n * 2 + 1) C[i][0] = C[i][i] = 1;
    for (int i = 1; i <= n * 2; i++) for (int j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]);
    rep(i, 100)rep(j, 100)dp[i][j] = -1;
    dp[0][0] = 0;
    int p = n, q = n;
    bool ng = 0;
    while (p != 0 && q != 0) {
        if (p > q)ng = 1;
        if (ng) {
            if (C[p + q - 1][p - 1] < k) {
                k -= C[p + q - 1][p - 1];
                cout << ")";
                q--;
            }
            else {
                cout << "(";
                p--;
            }
        }
        else {
            if (func(p - 1, q) < k) {
                k -= func(p - 1, q);
                cout << ")";
                q--;
            }
            else {
                cout << "(";
                p--;
            }
        }
    }
    while (p)cout << "(", p--;
    while (q)cout << ")", q--;
    cout << endl;
    return 0;
}