Codeforces #659 Div1 C. String Transformation 2

だから文字列の種類に制限があったか。
http://codeforces.com/contest/1383/problem/C

問題

基本的に以下の問題と同じシチュエーション。
ただし、違いは差し替え先の文字種が、差し替え元に対し大小どちらでも良い。
Codeforces #659 Div1 A. String Transformation 1 - kmjp's blog

解法

元の問題と同様に、20種類の文字に対応する20頂点を持つグラフに対し、A[i]→B[i]に対し辺を張る。
次に、各連結成分内について考える。

もしN要素の連結成分内任意の点から任意の点に移動可能にするには、各点を2周する2N回の差し替えが必要となる。
ただし、もしそのうちM要素がDAGを成している場合、このM要素をトポロジカルソートすると、
(N-M要素の点を適用にたどる)→(M要素をトポロジカルソートした順にたどる)→(N-M要素の点を適用にたどる)の順でたどると、2N-M-1回の差し替えで済むようになる。

よって、DAGを成す最大の点の集合を求めよう。これはBitDPで求めることができる。

int T;
int N;
string A,B;

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

int dag[1<<20];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		
		int ng=0;
		int E[26]={};
		UF<26> uf;
		FOR(i,N) {
			if(A[i]!=B[i]) {
				uf(A[i]-'a',B[i]-'a');
				E[A[i]-'a'] |= 1<<(B[i]-'a');
			}
		}
		
		ZERO(dag);
		x=0;
		dag[0]=1;
		for(int mask=1;mask<1<<20;mask++) {
			FOR(i,20) if(mask&(1<<i)) dag[mask]|=dag[mask^(1<<i)]&&((mask&E[i])==0);
			if(dag[mask]) x=max(x,__builtin_popcount(mask));
		}
		
		int ret=40-x;
		
		FOR(i,20) if(uf[i]==i) ret--;
		
		cout<<ret<<endl;
	}
}

まとめ

これ考察が割と難しくない？と思ったけど、本番もDの方が解かれてるな。