I - Which must be deleted?
Editorial
/
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
(
, )
のみからなる文字列のうち、以下のいずれかに該当するものを「正しい括弧列」といいます。
- 空文字列
- ある「正しい括弧列」A が存在して
(
, A,)
をこの順につなげた文字列 - ある空でない「正しい括弧列」A,\ B が存在して A,\ B をこの順につなげた文字列
長さ 4N で (
, )
のみからなる文字列 S と 2N 個の 2 整数の組 (L_i, R_i)\ (1\leq L_i < R_i \leq 4N) が与えられます。ここで、(L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の、(R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列です。
i=1, 2,\dots,2N の順に S の L_i,\ R_i 文字目のいずれかに印をつけた後、印をつけた文字のみを左から順に読み、長さ 2N の文字列として解釈したものを S' とします。
S' を「正しい括弧列」にできるか判定してください。
T 個のテストケースについて答えてください。
制約
- 入力される数値はすべて整数
- 1 \leq T \leq 1000
- 1 \leq N \leq 2000
- S は
(
,)
のみからなる長さ 4N の文字列 - 1 \leq L_i \leq 2N < R_i \leq 4N
- (L_1,L_2,\dots,L_{2N}) は (1,2,\dots,2N) の順列
- (R_1,R_2,\dots,R_{2N}) は (2N+1,2N+2,\dots,4N) の順列
- 1 つの入力に含まれるテストケースについて、 N の総和は 2000 以下
入力
入力は以下の形式で標準入力から与えられる。
T \mathrm{case}_1 \vdots \mathrm{case}_T
各ケースは以下の形式で与えられる。
N S L_1 R_1 L_2 R_2 \vdots L_{2N} R_{2N}
出力
T 行出力せよ。 i\ (1\leq i \leq T) 行目には i 番目のテストケースについて、S' を「正しい括弧列」にできる場合は Yes
を、できない場合は No
を出力せよ。
入力例 1
3 1 ()() 1 3 2 4 2 ))()((() 1 6 2 5 3 7 4 8 8 ))()))))()())((((()))(()(()))((( 8 26 2 25 1 18 4 22 7 17 12 32 10 31 5 30 15 27 9 23 13 19 11 24 14 29 6 28 16 20 3 21
出力例 1
Yes No Yes
1 番目のテストケースについて、 L_1=1 文字目と R_2=4 文字目に印をつけると S' は ()
となり、これは「正しい括弧列」です。
2 番目のテストケースについて、どのように印をつけても S' は「正しい括弧列」になりません。