問題一覧 > 通常問題

No.3147 Parentheses Modification and Rotation (RM Ver.)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 47
作問者 : Nauclhlt🪷 / テスター : naniwazu
1 ProblemId : 12277 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-05-16 22:54:21

注意

この問題は E とほぼ同じ設定です。$R, M$ の制約のみが異なります。

本問題への解をそのまま E に提出することでACできます。

問題文

対応が取れた括弧列の定義

文字列 $X$ が対応が取れた括弧列であるとは、次を満たすことをいいます。

  • $X$ に連続部分文字列として含まれる()を削除する操作を $0$ 回以上繰り返して $X$ を空文字列とすることができる

例えば()(())や()()()()は対応が取れた括弧列ですが、))((や)()()(などは対応が取れた括弧列ではありません。


長さ $N$ の文字列 $S$ があります。ここで $S$ は(および)から構成されます。

nauclhltくんは以下の操作を $0$ 回以上繰り返して、$S$ を対応が取れた括弧列にしようとしています。

操作

  • タイプ $1$ かタイプ $2$ の操作をどちらか選んで $1$ 回行う。
    • タイプ $1$: $S$ を右回転する。厳密には $S$ を、$S$ の $N$ 文字目と $S$ の $1$ 文字目から $N-1$ 文字目までを取り出した文字列をこの順に結合した文字列で置き換える。この操作ではコストが $R$ かかる
    • タイプ $2$: $1\leq i\leq N$ を満たす整数 $i$ と、文字 $c\in \lbrace $ ( $,$ ) $\rbrace$ を選び、$S$ の $i$ 文字目を $c$ で置き換える。この操作ではコストが $M$ かかる

nauclhltくんが操作によって $S$ を対応が取れた括弧列にすることは可能かどうかを判定し、可能ならコストの合計としてあり得る最小値を求めてください。

入力

$N$
$S$
$R$ $M$
  • $1\leq N\leq 10^5$
  • $0\leq R, M\leq 10^7$
  • $S$ は(および)からなる長さ $N$ の文字列
  • $N, R, M$ は整数

出力

$S$ を対応が取れた括弧列にすることが可能なら、コストの合計の最小値を $m$ として、次の形式で $1$ 行に出力してください。

$m$

不可能なら、-1を出力してください。

$-1$

最後に改行してください。

サンプル

サンプル1
入力
6
)()()(
1 1
出力
1

例えば、次のように操作すればコストの合計 $1$ で $S$ を対応が取れた括弧列にできます。

  • タイプ $1$ の操作を行う。コストが $1$ かかり、$S$ は()()()となる

なお、最適解を達成するような操作の手順は複数考えられる場合があります。

サンプル2
入力
4
)))(
1000 1
出力
3

操作手順の例:

  • $i=1, c=$(を選び、タイプ $2$ の操作を行う。コストが $1$ かかり、$S$ は())(となる
  • $i=3, c=$(を選び、タイプ $2$ の操作を行う。コストが $1$ かかり、$S$ は()((となる
  • $i=4, c=$)を選び、タイプ $2$ の操作を行う。コストが $1$ かかり、$S$ は()()となる

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。