また 1 つ、カッコ列に関する問題が誕生した
問題概要
長さ のカッコ列が与えられる。カッコ列に以下の操作を好きな順序で好きな回数だけ施して「整合が取れた状態」にしたい。
- カッコ列のある区間について、任意の順序に並び替える
- このときのコストは、区間の長さで与えられる
整合がとれた状態にするための最小コストを求めよ。不可能な場合は -1 を出力せよ。
制約
考えたこと
カッコ列でよくやる変数 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; } }