方針はあってたけど、本番中は通しきれず。
https://atcoder.jp/contests/abc261/tasks/abc261_g
問題
文字列S,Tの他、文字C[i]と文字列A[i]の対がK個与えられる。
S中の文字のうちいずれかのC[i]と一致するものを1つ選びA[i]で置き換える、という処理を繰り返してTにすることを考える。
Tにできるのであれば、最小処理回数を求めよ。
解法
自分は以下の2通りの関数をメモ化再帰してg(S,T)を求めることで対応した。
f(c,x) := 1文字cを、文字列xに変換可能か、可能なら最小処理回数
g(u,v) := 文字列uを、文字列vに変換可能か、可能なら最小処理回数
g(u,v)では、uの先頭1文字をvのprefix何文字かと変換可能か、f(c,x)を使い求める。
f(c,x)では、置き換え方をcから置き換え可能な全通り試し、g(A[i],x)のうち最小値を取る。
1点注意点として、1文字から1文字への変換ルールについては、メモ化再帰の順番が悪いと適切にメモ化されずWAしてしまう。
そこで、以下のコードでは1文字から1文字への変換については事前に列挙しておいてWarshal-Floyedで変換処理回数を求めておき、f(c,x)ではcを文字数が増える方向の変換のみ考えるようにした。
string S,T; int K; vector<string> A[26]; ll E[256][256]; map<string,ll> M[256]; map<pair<string,string>,ll> memo; ll hoge2(string a,string b); ll hoge(char c,string s) { if(s.empty()) return 1LL<<30; if(s.size()==1) return E[c][s[0]]; if(M[c].count(s)) return M[c][s]; ll& ret=M[c][s]; ret=1LL<<30; for(int a='a';a<='z';a++) if(E[c][a]<1LL<<30) { FORR(m,A[a]) ret=min(ret,1+E[c][a]+hoge2(m,s)); } return ret; } ll hoge2(string a,string b) { if(a==b) return 0; if(a.empty()) return 1LL<<30; if(a.size()>b.size()) return 1LL<<30; if(memo.count({a,b})) return memo[{a,b}]; if(a.size()==1) return hoge(a[0],b); ll& ret=memo[{a,b}]; ret=1LL<<30; int i; for(i=1;i<=b.size()-(a.size()-1);i++) { ll c=hoge(a[0],b.substr(0,i)); if(c<1LL<<30) ret=min(ret,c+hoge2(a.substr(1),b.substr(i))); } return ret; } void solve() { int i,j,k,l,r,x,y; string s; cin>>S>>T; cin>>K; FOR(x,256) FOR(y,256) E[x][y]=(x==y)?0:1<<30; FOR(i,K) { string a,b; cin>>a>>b; if(b.size()==1) { E[a[0]][b[0]]=1; } else { A[a[0]].push_back(b); } } FOR(k,256) FOR(x,256) FOR(y,256) E[x][y]=min(E[x][y],E[x][k]+E[k][y]); ll ret=hoge2(S,T); if(ret>=1LL<<30) { ret=-1; } cout<<ret<<endl; }
まとめ
メモ化再帰、ループが発生するケースは注意が必要だな…。