Codeforces #267 Div2 D. Fedor and Essay

やることはともかく、妙な問題設定だな。
http://codeforces.com/contest/467/problem/D

問題

M個の単語リストW[i]が与えられる。
また、N個の単語の対(A[i],B[i])からなる辞書が与えられる。

単語リスト中、いずれかA[i]に一致する単語はB[i]に置換することができる。
単語リストを適切に置換し、単語リスト中"R"の数を最小化せよ。
また、"R"の数が同じなら総単語長を最小化せよ。

解法

まず前処理として、単語リストや辞書中の単語の文字列にIDをふって、整数で処理できるようにしておく。

この問題は、Rの数が単語長よりも優先されるので、スコア＝("R"の数*でかい数+単語長)の総和を最小化する。
そして各単語から変換できる単語の最小スコアをDPで求めていく。

愚直な解法では、まず強連結成分分解をして辞書中の循環関係を解決し、トポロジカルソートした後DPすればよい。
しかし、もう少し簡単な解法として、今回のDPは最小値を求めるDPなので、priority_queueを使ってスコアの小さい順に単語のスコアを確定させ、その単語に変換可能な単語のスコアを確定するという処理を繰り返しても良い。
こちらだと強連結成分分解もトポロジカルソートもいらない。

int N,M;
string W[200000];
map<string,int> mp;
string F[200000],T[200000];
ll sc[400000];

vector<int> E[300000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>W[i];
		ITR(it,W[i]) *it=tolower(*it);
		mp[W[i]]=0;
	}
	cin>>M;
	FOR(i,M) {
		cin>>F[i]>>T[i];
		ITR(it,F[i]) *it=tolower(*it);
		ITR(it,T[i]) *it=tolower(*it);
		mp[F[i]]=mp[T[i]]=0;
	}
	i=0;
	ITR(it,mp) {
		it->second=i;
		sc[i]=(1LL<<40)*count(it->first.begin(),it->first.end(),'r')+it->first.size();
		i++;
	}
	FOR(i,M) E[mp[T[i]]].push_back(mp[F[i]]);
	priority_queue<pair<ll,int> > Q;
	FOR(i,mp.size()) Q.push(make_pair(-sc[i],i));
	while(!Q.empty()) {
		ll s=-Q.top().first;
		int k=Q.top().second;
		Q.pop();
		if(s!=sc[k]) continue;
		FOR(i,E[k].size()) {
			int tar=E[k][i];
			if(sc[tar]>sc[k]) {
				sc[tar]=sc[k];
				Q.push(make_pair(-sc[tar],tar));
			}
		}
	}
	
	ll tr=0,tl=0;
	FOR(i,N) {
		ll s=sc[mp[W[i]]];
		tr+=s>>40;
		tl+=s-((s>>40)<<40);
	}
	_P("%lld %lld\n",tr,tl);
	
	
}

まとめ

自分が最初思いついたのは、強連結成分分解＋トポロジカルソートだったけど、他人の回答見てこちらの簡潔な方法を知った。