Codeforces #659 Div1 A. String Transformation 1

このころ異様に調子悪かった時期だ。
http://codeforces.com/contest/1383/problem/A

問題

2つの文字列A,Bが与えられる。
Aに対し、以下の処理を行う。

• 同じ文字xを持つ、複数の文字を選択する。
• それらを同時に、より大きな文字yに差し替える。

AをBに変換可能な時、処理数の最小値を求めよ。

解法

A[i]＞B[i]となるiがある場合、変換不可。
それ以外の場合、A[i]とB[i]に対応する文字をunion findで連結していこう。
union-findで連結された文字は、必要に応じて連結成分内で1つずつ文字の種類を進めていくことができるので、処理回数の最小値としては、各連結成分について、(文字数-1)回数の処理を行えばよい。

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;
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B;
		
		int ng=0;
		int C[26]={};
		int T[26]={};
		UF<26> uf;
		FOR(i,N) {
			if(A[i]>B[i]) ng=1;
			if(A[i]<B[i]) {
				uf(A[i]-'a',B[i]-'a');
			}
		}
		
		int ret=0;
		
		FOR(i,20) if(uf[i]==i) ret+=uf.count(i)-1;
		if(ng==1) ret=-1;
		
		cout<<ret<<endl;
	}
}

まとめ

本番、文字種が20種であることに引っ張られ過ぎて無為な時間を過ごした。