https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring
前提知識
解説
二乗のDP解法はすぐに思いつく。
dp[i][diff] := 足りない部分のi文字目まで確定していて(の個数-)の個数がdiffのときの組み合わせ数
カッコの組み合わせといえばカタラン数であり、組み合わせは二項係数を使ってうまいこと計算が可能。
記憶している部分の(の個数をp, )の個数をmとする。
最終的に(と)の個数は一致している必要があるので、(の個数はpp=N-p, )の個数はmm=N-mとなる。
なので、Comb(pp+mm,pp)をすればだいたい良い。
大体いいが、途中で(の個数-)の個数が負になる可能性がある。
このパターンを引くが、これはカタラン数の計算で使われてるテクと同じテクを使おう。
元々の問題は切片1の所に直線があるが、今回は切片(diff+1)の所に直線が引かれることになるので、それで計算する。
本体の問題を解く前にpとmを数えて、既にdiffが負になっていないか、p,mがNを超えていないかをチェックしておこう。
int N, K; string S; //--------------------------------------------------------------------------------------------------- Comb<mint, 2010101> com; mint solve() { int p = 0, m = 0, diff = 0; rep(i, 0, K) { if (S[i] == '(') p++, diff++; else m++, diff--; if (diff < 0) return 0; } if (N < p) return 0; if (N < m) return 0; int pp = N - p; int mm = N - m; return com.aCb(pp + mm, pp) - com.aCb(pp + mm, mm - (diff + 1)); } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> K >> S; cout << solve() << endl; }