kmjp's blog

競技プログラミング参加記です

AtCoder ABC #261 : G - Replace

方針はあってたけど、本番中は通しきれず。
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;
	
}

まとめ

メモ化再帰、ループが発生するケースは注意が必要だな…。