Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 283 D問題 Scope

AtCoder ABC283 ABC D問題 400 pts

問題

提出解答

問題の概要

英小文字, ${\tt (}, {\tt )}$ からなる文字列のうち, 以下を満たすような文字列 $S$ を良い文字列という.

$S$ から英小文字を全て取り除いた文字列を $S'$ とする.
「 $S'$ にある連続する ${\tt ()}$ を取り除く」という操作をできるだけ行うと, 最終的に空文字列になる.

良い文字列 $S$ が与えられる. 各英小文字に対して, その英小文字が書かれたボールが1個ずつ, そして, 箱が1個ある.

高橋君は $i=1,2, \dots, |S|$ の順に気を失わない限り行う.

$S_i$ が英小文字のとき, その英小文字が書かれたボールを箱に入れる. ただし, そのボールが既に箱に入っている場合は気を失ってしまう.
$S_i={\tt (}$ のとき, 何もしない
$S_i={\tt )}$ のとき, $i$ 未満の正の整数 $j$ で, $S$ の $i$ 文字目から $j$ 文字目までの連続部分列が良い文字列になるような最大の整数を $j$ とする. $S$ の $j$ 文字目から $i$ 文字目に含まれている英小文字が書かれたボールを全て箱から取り出す.

高橋君はこの完遂できるか?

制約

$1 \leq |S| \leq 3 \times 10^5$
$S$ は良い文字列

解法

次のようにすることで正解することができる.

${\rm level} \gets 0, E \gets \emptyset, X_0 \gets \emptyset$ とする.
の順に以下を行う.
- が英小文字のとき
  - $S_i \in E$ ならば気を失う.
  - $S_i \not \in E$ ならば, $E, X_{{\rm level}}$ に $S_i$ を追加する.
- $S_i={\tt (}$ のとき, ${\rm level}$ を $1$ 加算する. その後, $X_{{\rm level}}$ を新たに用意し, 空集合で初期化する.
- $S_i={\tt (}$ のとき, $X_{{\rm level}}$ の各要素 $a \in X_{{\rm level}}$ に対して, $E$ から $a$ を削除する. その後, $X_{{\rm level}}$ (の内容) を削除し, ${\rm level}$ を $1$ 減算する.

上を完遂できれば答えは Yes, 途中で気絶すれば答えは No である.