AT_tenka1_2013_qualA_d 天下一展開

[problemUrl]: https://atcoder.jp/contests/tenka1-2013-quala/tasks/tenka1_2013_qualA_d あなたは友人のタクヤ君から独自の方式で圧縮された文字列とそれを展開した後に参照すべき部分の位置と長さを受け取ったので、 参照すべき部分の文字列を得るプログラムを作成する必要がある。 圧縮前の文字列は英字のみからなる文字列である。 そして、英字のみからなる部分文字列 $ x $ が $ n $ 回繰り返す部分を `($ x $)$ n $` に置換することで圧縮を行う。 ただし、$ |x|\ \geq\ 1 $、$ n\ \geq\ 1 $ とする。 ( $ |x| $ は $ x $ の文字列長 ) 例えば、 `ABABABA` は `(AB)3A` に置換することができる。 また、この置換操作は任意の回数行うことができる。 例えば、`AAABBAAABB` は `(AAABB)2` に置換した後、 さらに、`((A)3BB)2` 、 `((A)3(B)2)2` と置換することができる。 以上より、圧縮後の文字列 ( input ) は以下の[EBNF](http://ja.wikipedia.org/wiki/EBNF)に従う。 ``` input = string,{string} ; string = alphabet,{alphabet} | "(",input,")",positive_number ; alphabet = "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" ; positive_number = digit_excluding_zero,{digit} ; digit_excluding_zero = "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" ; digit = "0" | digit_excluding_zero ; ``` 入力は以下の形式で標準入力から与えられる。 > $ B $ $ L $ $ N $ $ S $ - $ 1 $ 行目には、展開後に参照するべき部分の開始位置 $ B $ ( $ -M\ \leq\ B\ \lt\ M $ ) 、参照するべき長さ $ L $ ( $ 1\ \leq\ L\ \leq\ 10^5 $ ) 、 圧縮後の文字列の長さ $ N $ ( $ 1\ \leq\ N\ \leq\ 10^4 $ ) が、スペースで区切られて、それぞれ整数で与えられる。 ただし、$ M $ は圧縮前の文字列の長さ とする。 - $ 2 $ 行目には、圧縮後の文字列 $ S $ が与えられる。 - $ B $ は、非負の場合は先頭を $ 0 $ とした先頭からの位置を表し、負の場合は末尾を $ -1 $ とした末尾からの位置を表す。 - $ B $ の正負に関係なく、開始位置から末尾方向への $ L $ 文字が参照すべき文字列であり、この長さの文字列が得られることは保証される。 - 圧縮前の文字列の長さは $ 10^{15} $ を超えない。 - 圧縮前の文字列の長さを$ M $とし、 $ L,\ N\ \leq\ 100 $, $ M\ \leq\ 1000 $ の入力に正解すると、130 点満点に対して部分点として 50 点が与えられる。 - $ L,\ N\ \leq\ 100 $ の入力に正解すると、130 点満点に対して部分点として、さらに 50 点が与えられる。 参照するべき文字列を標準出力に $ 1 $ 行で出力せよ。 なお、行の終端には改行が必要である。 ``` 0 7 6 (AB)3A ``` ``` ABABABA ``` ``` -6 5 11 ((A)3(B)2)2 ``` ``` BAAAB ```

N/A

N/A