問題一覧 > 通常問題

No.2145 Segment +-

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : milkcoffeemilkcoffee / テスター : hamamuhamamu nok0nok0
5 ProblemId : 8577 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-25 22:34:39

問題文

長さ $N$ の +,-,? からなる文字列 $S$ が与えられます。あなたは以下のルールに従って長さ $N$ の整数列 $A$ を作ります。

ここで、$S_i$ は文字列 $S$ の $i$ 文字目、 $A_i$ は整数列 $A$ の $i$ 番目の要素を表します。

  • $S_i=$+ なら $A_i=1$ にする。
  • $S_i=$- なら $A_i=-1$ にする。
  • $S_i=$? なら $A_i=1$ または $A_i=-1$ にする。

作られた $A$ に対して、以下の問題の答えを $f(A)$ とします。

長さ $N$ の整数列 $A$ があり、 $A$ に対して以下の操作を行うことができます。

  • 整数 $l,r \ (1 \leq l \leq r \leq N)$ を選び、 $A_l, A_{l+1}, \cdots , A_r$ それぞれの値を $-1$ 倍する。

以下の条件を達成するために必要な操作回数の最小値を求めてください。

  • 条件:$B_i= \sum_{j=1}^{i} A_j$ とする。全ての $i$ について、 $B_i \geq 0$ が成り立つ。

$f(A)$ の 最小値 を求めてください。

入力

$N$
$S$

  • $1 \leq N \leq 2 \times 10^5$
  • $S$ は +,-,? からなる長さ $N$ の文字列
  • $N$ は整数である。

出力

$f(A)$ の 最小値 を整数で出力してください。

サンプル

サンプル1
入力
5
+--?-
出力
1

$A$ として考えられるのは $(1,-1,-1,1,-1), (1,-1,-1,-1,-1)$ の $2$ 通りです。
例えば $A=(1,-1,-1,1,-1)$ のとき、$B=(1,0,-1,0,-1)$ です。
$l=2, r=3$ として操作を行うと $A=(1,1,1,1,-1)$ $B=(1,2,3,4,3)$ となります。
$1$ 回の操作で条件を達成することができたため、この場合は $f(A)=1$ です。
$A=(1,-1,-1,-1,-1)$ の場合でも $f(A)=1$ です。よって、$f(A)$ の最小値は $1$ です。

サンプル2
入力
4
??--
出力
0

$A=(1,1,-1,-1)$ のときのみ、 $f(A)=0$ となります。

サンプル3
入力
13
-?+++---?----
出力
2

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