競技プログラミング用 知識集積所
ABC428C - Brackets Stack Query
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 特になし
考え方
良い括弧列の定義通りのまま確認するのでは判定に時間がかかる。
そこで、別の確認方法を行う。
そこで、別の確認方法を行う。
括弧列の各箇所に対し、そこより左を見たときに '(' が ')' より何個多いかを考える。
例えば、"(*1)" の6文字だったら、一番左右と文字の間の計7か所に対して考えて、{0,1,2,1,2,1,0} の7要素のvectorを対応させる。
これは、先頭を0とし、'('だったら左より1大きくし、')'だったら左より1小さくすることで作ることができる。
このとき、良い括弧列の条件は、作ったvectorの全ての要素が0以上であり、かつ末尾が0であることである。
例えば、"(*1)" の6文字だったら、一番左右と文字の間の計7か所に対して考えて、{0,1,2,1,2,1,0} の7要素のvectorを対応させる。
これは、先頭を0とし、'('だったら左より1大きくし、')'だったら左より1小さくすることで作ることができる。
このとき、良い括弧列の条件は、作ったvectorの全ての要素が0以上であり、かつ末尾が0であることである。
この問題では末尾しか操作しないので、1回のクエリごとにvectorの末尾を1つ伸ばすか縮めるかするだけで済み、vector作成は十分高速に行える。
末尾の0判定も、もちろんすぐにできる。
問題は全ての要素が0以上というところだが、これはvector内で最初に負の数が出てくる位置を管理することで高速にできる。
具体的には、
末尾の0判定も、もちろんすぐにできる。
問題は全ての要素が0以上というところだが、これはvector内で最初に負の数が出てくる位置を管理することで高速にできる。
具体的には、
- 値が-1になったときに位置の記録がなかったら、その位置を記録
- 値が-1になったが位置の記録が存在していたら何もしない
- 縮めたときに、位置の記録より短くなったら記録を消す
でよい。
