SRM 438 Div 1 Medium EndlessStringMachine
フラクタルっぽい再帰の長い列をつくってその一部を求めなさい系問題。
問題
文字列inputを読み込んで、与えられた文字列programの全ての'$'をinputで置き換えるという操作がある。
この操作を、初回をinput、次回からはその出力を新たなinputとしてs回行って出来る文字列を考える。
この文字列のmin番目からmax番目を求めよ。
制約条件
input, programは50文字以下。programは必ず$で開始。
s, min, maxは10億以下。
方針
文字列のi番目を求める関数を作りたい。
その準備に、操作をn回施した文字列の長さを求める関数を作る。
これは再帰を使えば簡単。min,maxは10億以下なので、10億を超えたら適当に打ち切る。
ただし$がprogram中に一個だけの場合は（文字列の長さが再帰回数の線形になるため）再帰を使うと間に合わないので直接計算する。
そしたらi番目を求める関数を書く。関数にsは引数として持たせる。
get(s,i)みたいな感じ。
programのj文字目が$だったら、
- len(s-1)がi以上だったらget(s-1,i)を求めればいい。
- len(s-1)がi未満だったら、iからlen(s-1)を引いて次の文字を見る。
ただし「len(s-1)がi以上だったらget(s-1,i)を求める」という部分を愚直にやるとTLEするので、ちょうどlen(s-2)はi未満でlen(s-1)がi以上になるようなsを二分探索で探す。
