AtCoder Beginner Contest 283 D問題 Scope
問題
提出解答
問題の概要
英小文字, からなる文字列のうち, 以下を満たすような文字列
を良い文字列という.
から英小文字を全て取り除いた文字列を
とする.
- 「
にある連続する
を取り除く」という操作をできるだけ行うと, 最終的に空文字列になる.
良い文字列 が与えられる. 各英小文字に対して, その英小文字が書かれたボールが1個ずつ, そして, 箱が1個ある.
高橋君は の順に気を失わない限り行う.
が英小文字のとき, その英小文字が書かれたボールを箱に入れる. ただし, そのボールが既に箱に入っている場合は気を失ってしまう.
のとき, 何もしない
のとき,
未満の正の整数
で,
の
文字目から
文字目までの連続部分列が良い文字列になるような最大の整数を
とする.
の
文字目から
文字目に含まれている英小文字が書かれたボールを全て箱から取り出す.
高橋君はこの完遂できるか?
制約
は良い文字列
解法
次のようにすることで正解することができる.
とする.
の順に以下を行う.
が英小文字のとき
ならば気を失う.
ならば,
に
を追加する.
のとき,
を
加算する. その後,
を新たに用意し, 空集合で初期化する.
のとき,
の各要素
に対して,
から
を削除する. その後,
(の内容) を削除し,
を
減算する.
上を完遂できれば答えは Yes, 途中で気絶すれば答えは No である.