Description:
A-Zのアルファベットから構成された遺伝子の繰り返し部分を、繰り返し数(繰り返された遺伝子)という形式で圧縮する事が出来る。
この圧縮は、ネストさせる事が可能だ。(つまり、ABABCABABCという遺伝子は、2(2(AB)C)という圧縮が可能である)
また、繰り返された遺伝子の長さが1の時は、それを囲む()を省略しても良い。
ある遺伝子の圧縮形(長さは1から100)が与えられた時、元の遺伝子のi番目(0<=i<=100万)のアルファベットをを答えよ。
元の遺伝子が短く、i番目が存在しない時は、0を出力せよ。
Answer:
圧縮形式をツリーで表現し、各ツリーの展開後の長さを再帰的に求めればよい。
長さは1000*1000*1000*...と、とてつもない長さになるので、長さは最大で100万+1などというように切捨てる必要がある。
繰り替えさない文字でも、一回の繰り返しの...と扱ってしまうと、処理が統一できて楽になる。
Source: