AtCoder ABC #175 : F - Making Palindrome

実装がややめんどい。
https://atcoder.jp/contests/abc175/tasks/abc175_f

問題

N個の文字列S[i]と、それぞれの追加コストC[i]が与えられる。
重複を許して各文字列を任意に選んで連結し、空でない回文となる文字列を作りたい。
その際、文字列S[i]を1回使うとコストC[i]がかかる。
条件を満たす最小コストを求めよ。

解法

まず回文の真ん中となる文字列および真ん中の文字の位置を総当たりしよう。
先頭または末尾に不足があって何文字か足せば回文になる場合、

• 足すべきは先頭と末尾のどちらか
• 追加で足すべき文字列は何か

を状態として持ち、Dijkstra法の要領でコストの低い状態に対して、足すべき文字列が0になるまで先頭または末尾に文字列を足していこう。
イメージとしては、末尾と先頭に足りない方にどんどん足していって、最終的に帳尻が合うのを待つ感じ。

一件状態数が多そうだが、状態は文字列のprefixかsuffixなので取りえる状態はO(N*|S|)通り程度で状態遷移もO(N)通りなので、計算量は文字列比較を雑にやってもO(N^2*|S|^2)で済み、実行時間はかなり余裕があるはず。

int N;
string S[55];
ll C[55];

map<string,ll> cost[2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>S[i]>>C[i];
		for(j=0;j<=S[i].size();j++) {
			FOR(y,2) {
				string A=S[i].substr(0,j);
				if(y==1&&j==0) continue;
				if(y==1) A.pop_back();
				string B=S[i].substr(j);
				reverse(ALL(A));
				x=min(A.size(),B.size());
				if(B.substr(0,x)==A.substr(0,x)) {
					if(A.size()<B.size()) {
						string D=B.substr(x);
						if(cost[1].count(D)==0) cost[1][D]=1LL<<60;
						cost[1][D]=min(cost[1][D],C[i]);
					}
					else {
						string D=A.substr(x);
						if(cost[0].count(D)==0) cost[0][D]=1LL<<60;
						cost[0][D]=min(cost[0][D],C[i]);
					}
					
				}
			}
		}
	}
	priority_queue<pair<ll,pair<int,string>>> PQ;
	FOR(i,2) FORR(c,cost[i]) {
		PQ.push({-c.second,{i,c.first}});
	}
	
	while(PQ.size()) {
		ll co=-PQ.top().first;
		int type=PQ.top().second.first;
		string cur=PQ.top().second.second;
		PQ.pop();
		if(cost[type][cur]!=co) continue;
		if(cur=="") {
			cout<<co<<endl;
			return;
		}
		
		FOR(i,N) {
			string A;
			string B;
			if(type==1) {
				A=S[i];
				B=cur;
				reverse(ALL(A));
			}
			else {
				A=cur;
				B=S[i];
			}
			x=min(A.size(),B.size());
			if(A.substr(0,x)==B.substr(0,x)) {
				if(A.size()<B.size()) {
					string D=B.substr(x);
					if(cost[1].count(D)==0) cost[1][D]=1LL<<60;
					if(co+C[i]<cost[1][D]) {
						cost[1][D]=co+C[i];
						PQ.push({-cost[1][D],{1,D}});
					}
				}
				else {
					string D=A.substr(x);
					if(cost[0].count(D)==0) cost[0][D]=1LL<<60;
					if(co+C[i]<cost[0][D]) {
						cost[0][D]=co+C[i];
						PQ.push({-cost[0][D],{0,D}});
					}
				}
			}
		}
		
	}
	cout<<-1<<endl;
	
	
}

まとめ

最近のABCの中では実装が重い方？もっと楽に書けるかな。