[1] 正しい括弧列の言い換え

正しい括弧列という条件は，( と ) の個数が等しく，( を \(+1\) ，) を \(-1\) に置き換えて得られる数列の累積和の最小値が \(0\) であるという条件で言い換えられます．

言い換え後の条件のほうが考えやすいので，以下そちらを考えます．

[2] 解法

\(1\) 番目の操作では ( の個数は変化しないので，\(2\) 番目の操作によって ( と ) の個数を揃える必要があります．

( の個数を \(p\)，) の個数を \(m\) とすると，必要な \(2\) 番目の操作回数は \(\frac{|p-m|}{2}\) と求められます．

どの (,) を置き換えるかは，言い換え後の条件より ( を ) に置き換える場合は右にあるものから，) を ( に置き換える場合は左にあるものから置き換える方法が最適であることが分かります．

次に，\(1\) 番目の操作により「 ( を \(+1\) ，) を \(-1\) に置き換えて得られる数列の累積和の最小値が \(0\) である」という条件を満たすために必要な操作回数を考えます．

\(2\) 番目の操作に関する議論と同様に，一番左の ) と 一番右の ( を入れ替える操作のみを考えればよいです．一回の操作で累積和の最小値は \(2\) 増えることから，必要な操作回数は累積和の最小値を \(l\) としたとき，\(\lceil\frac{-l}{2}\rceil\) と求めることができます．

\(1\) 番目の操作は \(2\) 番目の操作 \(2\) 回によって実現できるため，\(A\) を \(\min{(A,2B)}\) で置き換えておく必要があることに注意してください．

以上の処理は全て \(\mathrm{O}(N)\) で行えます．

[3] 実装例(C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    long long a, b;
    cin >> n >> a >> b;
    a = min(a, 2 * b);
    string s;
    cin >> s;
    int p = count(s.begin(), s.end(), '(');
    int m = 2 * n - p;
    int d = p - m;
    long long res = 0;
    if(p > m) {
        for(int i = 2 * n - 1; i >= 0; --i) {
            if(s[i] == '(' and d) {
                d -= 2;
                s[i] = ')';
                res += b;
            }
        }
    } else {
        for(int i = 0; i < 2 * n; i++) {
            if(s[i] == ')' and d) {
                d += 2;
                s[i] = '(';
                res += b;
            }
        }
    }
    long long cum = 0, mn = 0;
    for(int i = 0; i < 2 * n; i++) {
        cum += (s[i] == '(' ? 1 : -1);
        mn = min(mn, cum);
    }
    res += (-mn + 1) / 2 * a;
    cout << res << endl;
}

[4] 余談

実はこの問題は \(1\) 番目の操作が隣接スワップの場合でも解けます。興味がある方は考えてみてください。