No.2145 Segment +-
タグ : / 解いたユーザー数 24
作問者 :
milkcoffee
/ テスター :
hamamu
nok0
問題文
長さ $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もしくは右上の雲マークをクリックしてアカウントを作成してください。