TopCoder SRM 834 : Div1 Easy Div2 Hard MatchingPatterns

4問だったのは意図的なものなのかミスなのか…。
https://community.topcoder.com/stat?c=problem_statement&pm=17756

問題

N個の文字列型変数がある。各変数は1文字の大文字で表現され、アルファベット小文字からなる文字列を格納する。
各変数のサイズが入力として与えられる。加えて、いくつかの文字列パターンが与えられる。
文字列パターンは大文字小文字混在の文字列であり、大文字の部分を対応する変数の中身を挿入すると、いずれも同じ文字列を示しているものとする。

文字列パターンが示す文字列のうち、上記条件に矛盾しないものがあれば1つ例を答えよ。

解法

変数の長さはわかっているので、まず各パターンが同じ長さの文字列を表すことを確認しよう。
次に、パターン同士を比較すると

• この変数の何文字目とこの変数の何文字目は、等しくなければならない
• この変数の何文字目は、この小文字でなければならない

という条件が多数現れる。
union-findを使いこのような同値関係を管理していく。
もし途中で2つの異なる小文字が同値となってしまう場合、解なし。
そうでない場合、小文字と同値になる変数中の1文字は、その小文字に置き換えればよいし、そうでないものはすべて'a'に置き換えてしまおう。

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 num=um) {int i; FOR(i,num) 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;
	}
};

class MatchingPatterns {
	public:
	string solve(int N, vector <int> L, vector <string> patterns) {
		UF<6000> uf;
		char C[6000];
		vector<int> P[55];
		string S;
		int i,j;
		FOR(i,patterns.size()) {
			FORR(c,patterns[i]) {
				if(c>='a'&&c<='z') {
					P[i].push_back(c-'a');
				}
				else {
					c-='A';
					FOR(j,L[c]) P[i].push_back((c+1)*50+j);
				}
			}
			if(i) {
				if(P[i].size()!=P[0].size()) return "";
				FOR(j,P[0].size()) uf(P[0][j],P[i][j]);
			}
		}
		ZERO(C);
		FOR(i,26) {
			if(C[uf[i]]) return "";
			C[uf[i]]='a'+i;
		}
		FOR(i,6000) if(C[i]==0) C[i]='a';
		FORR(c,P[0]) S+=C[uf[c]];
		return S;
		
		
		
	}
}

まとめ

1問目はDiv2Medium相当っぽいので省略。