けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #626 (Div. 1) A. Unusual Competitions (R1300)

また 1 つ、カッコ列に関する問題が誕生した

問題へのリンク

問題概要

長さ  N のカッコ列が与えられる。カッコ列に以下の操作を好きな順序で好きな回数だけ施して「整合が取れた状態」にしたい。

  • カッコ列のある区間について、任意の順序に並び替える
  • このときのコストは、区間の長さで与えられる

整合がとれた状態にするための最小コストを求めよ。不可能な場合は -1 を出力せよ。

制約

  •  1 \le N \le 10^{6}

考えたこと

カッコ列でよくやる変数 cnt を導入して、最初は cnt = 0 で初期化して

  • 左カッコに対しては cnt += 1
  • 右カッコに対しては cnt -= 1

とする。このとき、「一度も負にならない」「最終的に 0 になる」というのがカッコ列が整合するための必要十分条件となる。

さて、与えられたカッコ列に対してどのように操作しても cnt の最終値は変化しないので、それが 0 でなければ -1 を出力する。0 ならば一応は可能である。

答えは結局、cnt が負の値をとる範囲の長さになる。その長さ分のコストは確実に支払う必要があり、逆にそれだけのコストで達成できる。

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

int N;
string S;

int solve() {
    int res = 0;
    int cur = 0, nex;
    for (int i = 0; i < N; ++i) {
        nex = cur;
        if (S[i] == '(') ++nex;
        else --nex;
        if (cur < 0 || nex < 0) ++res;
        cur = nex;
    }
    if (nex != 0) return -1;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); 
    while (cin >> N >> S) {
        cout << solve() << endl;
    }
}