英大文字1つを英大/小文字からなる0文字以上10文字以下の列に書き換えるというルールがn個与えられる。(1 <= n <= 50)
このルールを何回か適用して、 S を英語小文字のみからなる文字列に書き換える。
ちょうど l 文字で、辞書順最小のものを答えよ。(0<= l <= 20)
答えが存在しないときは、 - と出力せよ。
次のような手順で解を求める事が出来る。
1. ルールを単純な形のみで表現する("X=", "X=aY", "X=YZ"のみ)
2. 空文字列になりえる変数を列挙する
3. "X=Y"という形のルールでありえるものを全て列挙する
4. 各変数が取り得るn文字で辞書式最小の文字列を計算する
1. ルールを単純な形のみで表現する
"N="というルールを持つ新しい変数Nを導入する。
これを用いてルールを "X="、 "X=xY"もしくは、"X=YZ"のみの等価な形に変換する。
例えば、"A=bCd"は、新しい変数X, Yを用いて、"A=bX", "X=CY", "Y=dN"と書け、"A=a"は、"A=aN"と書ける。
この変換が終わった後の変数、ルールの数は、500個以下である。(26 + 1 + 50 * (10-1))
この段階での変数の数をV、ルールの数をEとする。
2. 空文字列になりえる変数を列挙する
まず、"X="の形のルールを持つ変数は空文字列になりうる。
そして、Y, Zが空文字になりえるなら、 "X=YZ"のルールを持つXも空文字になりえる。
多くてもルールの数と同じ回数だけ"X=YZ"の伝播が起これば列挙が終了する為、O(V*E)で計算を行う事が出来る。
3. "X=Y"という形のルールでありえるものを全て列挙する
"X=YZ"もしくは"X=ZY"の形のルールがあり、Zが空文字になりえるなら、XがYに変化しうる。
このようなルールをXからYへの枝とみなし、Xを起点としてDFSを行う事で、Xが変化しうる変数全てをO(E)で求める事が出来る。
全部の変数を起点にしてこれを行う事で、 O(V*E)で全ての"X=Y"の形をしたルールを列挙する事が出来る。
このルールの数は最大でV^2個存在する。
4. 各変数が取り得るn文字で辞書式最小の文字列を計算
変数Xが取りえる長さnの辞書式最小の文字列をtbl[n][X]で持ってこれるようなテーブルを、n=0, n=1, ....., n=lの順番で埋めていく。
単純に適当な順番で全てのルールを見ていくだけでは、複数のルールで循環参照が起こる時に問題となる為、
"X=aY", "X=YZ" のルールで作れるものを全ての変数で作った後に、"X=Y"のルールを行う必要がある。
手順1は手順4の、手順2は手順3の、手順3は手順4の計算量を減らす為に必要となる。
この手順の計算量は、 nをまわした回数* ("X=aY","X=Y"のルールの数 + "X=YZ"のルールの数 * n) *文字列比較にかかる時間 = l^2*(E*l+ V^2) となる。
求める答えは、 tbl[l][S]となる。