CF 1709C Recover an RBS

給定一個由 ”?”，”(”，”)” 組成的字串，”?” 可以替換成 ”(” 或 ”)“，問是否有僅有一種方法使得字串是正確的括號序列。

設 $dep$ 表示括號序列的棧大小，遇到 ”(” 則 $dep + 1$，遇到 ”)” 則 $dep - 1$，所謂的正確括號序列則是在任意時刻 $dep \ge 0$ 且最後 $dep = 0$。

首先考慮將原字串還原成一個括號序列。由於要滿足 $dep \ge 0$ 因此優先填 ”(“。然後考慮將其轉成不同的括號序列，在 ”(” 與 ”)” 交界的地方交換，保證這個交換對棧的大小的影響最小。

bool check(const std::string &s)
{
    int dep = 0;
    for (auto i : s)
    {
        if (i == '(') dep++;
        if (i == ')') dep--;
        if (dep < 0) return false;
    }
    return dep == 0;
}

void solve()
{
    std::string s;
    std::cin >> s;
    int n = s.size();
    std::vector<int> pos;
    int lcnt = n / 2, rcnt = n / 2;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '?') pos.emplace_back(i);
        if (s[i] == '(') lcnt--;
        if (s[i] == ')') rcnt--;
    }
    if (lcnt == 0 || rcnt == 0)
    {
        puts("Yes");
        return ;
    }

    int tmp = -1;
    for (int i = 0, __end = pos.size(); i < __end; i++)
    {
        if (i < lcnt) s[pos[i]] = '(';
        else
        {
            s[pos[i]] = ')';
            if (tmp == -1) tmp = i;
        }
    }
    std::swap(s[pos[tmp]], s[pos[tmp - 1]]);
    if (check(s)) puts("No");
    else puts("Yes");
}