D - Colorful Bracket Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

6 種類の文字、(, ), [, ], <, > からなる文字列 S が与えられます。

ここで、文字列 T は、以下の条件を満たすときカラフル括弧列と呼ばれます。

以下の操作を何回か（0 回でも良い）繰り返すことで、T を空文字列にできる。

  • T の（連続する）部分文字列であって、(), [], <> のいずれかであるようなものが存在するとき、そのうちの 1 つを選んで削除する。
  • 削除された部分文字列が T の先頭または末尾であるとき、残りの文字列を新たに T とする。
  • そうでないとき、削除された前後の文字列を 1 つに連結し、新たに T とする。

S がカラフル括弧列であるか判定してください。

制約

  • S は長さ 1 以上 2\times 10^5 以下の文字列
  • S は (, ), [, ], <, > のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

S

出力

S がカラフル括弧列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

([])<>()

出力例 1

Yes

S=([])<>() に対して、次のように操作を繰り返すことで空文字列にすることができます。

  • ([])<>() の 2 文字目から 3 文字目までをとった部分文字列 [] を削除し、前後を連結する。文字列は新たに ()<>() となる。
  • ()<>() の 1 文字目から 2 文字目までをとった部分文字列 () を削除する。文字列は新たに <>() となる。
  • <>() の 1 文字目から 2 文字目までをとった部分文字列 <> を削除する。文字列は新たに () となる。
  • () の 1 文字目から 2 文字目までをとった部分文字列 () を削除する。文字列は空文字列となる。

よって、S=([])<>() はカラフル括弧列であるため、Yes を出力します。

入力例 2

([<)]>

出力例 2

No

S=([<)]> は (), [], <> を部分列として含まないため、1 回目の操作を行うことができず、特に S はカラフル括弧列ではありません。よって、No を出力します。

入力例 3

())

出力例 3

No

S に対して操作を繰り返し、空文字列とすることはできません。
よって、S はカラフル括弧列ではないため、No を出力します。

Score : 400 points

Problem Statement

You are given a string S consisting of six types of characters: (, ), [, ], <, >.

A string T is called a colorful bracket sequence if it satisfies the following condition:

It is possible to turn T into an empty string by repeating the following operation any number of times (possibly zero):

  • If there exists a contiguous substring of T that is one of (), [], or <>, choose one such substring and delete it.
  • If the deleted substring was at the beginning or end of T, the remainder becomes the new T.
  • Otherwise, concatenate the part before the deleted substring and the part after the deleted substring, and that becomes the new T.

Determine whether S is a colorful bracket sequence.

Constraints

  • S is a string of length between 1 and 2\times 10^5, inclusive.
  • S consists of (, ), [, ], <, >.

Input

The input is given from Standard Input in the following format:

S

Output

If S is a colorful bracket sequence, print Yes; otherwise, print No.

Sample Input 1

([])<>()

Sample Output 1

Yes

For S=([])<>(), it is possible to turn it into an empty string by repeating the operation as follows:

  • Delete the substring [] from the 2nd to the 3rd character in ([])<>(), then concatenate the parts before and after it. The string becomes ()<>().
  • Delete the substring () from the 1st to the 2nd character in ()<>(). The string becomes <>().
  • Delete the substring <> from the 1st to the 2nd character in <>(). The string becomes ().
  • Delete the substring () from the 1st to the 2nd character in (). The string becomes empty.

Thus, S=([])<>() is a colorful bracket sequence, so print Yes.

Sample Input 2

([<)]>

Sample Output 2

No

Since S=([<)]> does not contain (), [], or <> as a contiguous substring, we cannot perform the 1st operation, and in particular S is not a colorful bracket sequence. Therefore, print No.

Sample Input 3

())

Sample Output 3

No

It is impossible to turn S into an empty string by repeating the operations.
Therefore, S is not a colorful bracket sequence, so print No.