/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
英小文字、(、) からなる文字列のうち、以下の手順によって空文字列になるものを良い文字列と呼びます:
- まず、英小文字をすべて削除する。
- 次に、連続する
()が存在する限り、それを削除する。
例えば、((a)ba) は英小文字をすべて削除すると (()) となり、2 文字目と 3 文字目に連続する () を削除すると () となり、最終的に空文字列にすることができるので良い文字列です。
良い文字列 S が与えられます。 S の i 文字目を S_i で表します。
各英小文字 a , b , \ldots , z に対して、その文字が書かれたボールが 1 つあります。
また、空の箱があります。
高橋君は i = 1,2, \ldots ,|S| に対してこの順に気を失わない限り操作を行います。
- S_i が英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
- S_i が
(ならば、何もしない。 - S_i が
)ならば、i 未満の整数 j であって、S の j 番目から i 番目までの文字からなる文字列が良い文字列となる最大の整数 j を取る。（このような整数 j は必ず存在することが証明できる。）j 番目から i 番目までの操作で箱に入れたボールをすべて、箱から取り出す。
高橋君が気を失わずに一連の操作を完了させられるか判定してください。
制約
- 1 \leq |S| \leq 3 \times 10^5
- S は良い文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
高橋君が気を失わずに一連の操作を完了させられる場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
((a)ba)
出力例 1
Yes
i = 1 のとき、高橋君は何もしません。
i = 2 のとき、高橋君は何もしません。
i = 3 のとき、高橋君は a の書かれたボールを箱の中に入れます。
i = 4 のとき、4 未満の整数 j であって、S の j 番目から 4 番目までの文字からなる文字列が良い文字列となる最大の整数は 2 であるため、高橋君は a の書かれたボールを箱から取り出します。
i = 5 のとき、高橋君は b の書かれたボールを箱の中に入れます。
i = 6 のとき、高橋君は a の書かれたボールを箱の中に入れます。
i = 7 のとき、7 未満の整数 j であって、S の j 番目から 7 番目までの文字からなる文字列が良い文字列となる最大の整数は 1 であるため、高橋君は a の書かれたボールと b の書かれたボールを箱から取り出します。
したがってこの場合の答えは Yes となります。
入力例 2
(a(ba))
出力例 2
No
i = 1 のとき、高橋君は何もしません。
i = 2 のとき、高橋君は a の書かれたボールを箱の中に入れます。
i = 3 のとき、高橋君は何もしません。
i = 4 のとき、高橋君は b の書かれたボールを箱の中に入れます。
i = 5 のとき、a の書かれたボールはすでに箱に入っているため、高橋君は気を失い、これ以降の操作は行われません。
したがってこの場合の答えは No となります。
入力例 3
(((())))
出力例 3
Yes
入力例 4
abca
出力例 4
No
Score : 400 points
Problem Statement
A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:
- First, remove all lowercase English letters.
- Then, repeatedly remove consecutive
()while possible.
For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the 2-nd and 3-rd characters to obtain (), which in turn ends up in an empty string.
You are given a good string S. We denote by S_i the i-th character of S.
For each lowercase English letter a, b, \ldots, and z, we have a ball with the letter written on it.
Additionally, we have an empty box.
For each i = 1,2, \ldots ,|S| in this order, Takahashi performs the following operation unless he faints.
- If S_i is a lowercase English letter, put the ball with the letter written on it into the box. If the ball is already in the box, he faints.
- If S_i is
(, do nothing. - If S_i is
), take the maximum integer j less than i such that the j-th through i-th characters of S form a good string. (We can prove that such an integer j always exists.) Take out from the box all the balls that he has put in the j-th through i-th operations.
Determine if Takahashi can complete the sequence of operations without fainting.
Constraints
- 1 \leq |S| \leq 3 \times 10^5
- S is a good string.
Input
The input is given from Standard Input in the following format:
S
Output
Print Yes if he can complete the sequence of operations without fainting; print No otherwise.
Sample Input 1
((a)ba)
Sample Output 1
Yes
For i = 1, he does nothing.
For i = 2, he does nothing.
For i = 3, he puts the ball with a written on it into the box.
For i = 4, j=2 is the maximum integer less than 4 such that the j-th through 4-th characters of S form a good string, so he takes out the ball with a written on it from the box.
For i = 5, he puts the ball with b written on it into the box.
For i = 6, he puts the ball with a written on it into the box.
For i = 7, j=1 is the maximum integer less than 7 such that the j-th through 7-th characters of S form a good string, so he takes out the ball with a written on it, and another with b, from the box.
Therefore, the answer to this case is Yes.
Sample Input 2
(a(ba))
Sample Output 2
No
For i = 1, he does nothing.
For i = 2, he puts the ball with a written on it into the box.
For i = 3, he does nothing.
For i = 4, he puts the ball with b written on it into the box.
For i = 5, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.
Therefore, the answer to this case is No.
Sample Input 3
(((())))
Sample Output 3
Yes
Sample Input 4
abca
Sample Output 4
No