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; }