はまやんはまやんはまやん

hamayanhamayan's blog

Brackets Restoring [EEIC Programming Contest #0 D]

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring

前提知識

解説

https://www.hackerrank.com/contests/eeic-programming-contest-0/challenges/brackets-restoring/submissions/code/1318663832

二乗の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;
}