Codeforces ECR #103 : E. Pattern Matching

終盤がかなり難しかった回。
https://codeforces.com/contest/1476/problem/E

問題

N個のパターンと、M個の文字列が与えられる。
各パターンと文字列はK文字からなる。パターンの各文字はアルファベットかワイルドカードである。
なお、同じパターンは複数存在しない。

今、このパターンを任意に並べ替えたとする。
各文字列に対し、最初に一致するパターン番号が与えられる。
条件を満たすパターンの並べ方が存在すればそれを答えよ。

解法

同じパターンが複数存在することはないので、各文字列と一致するパターンは高々2^K通りである。
各文字列が最初に一致するパターン番号より、この2^K通りのうち最初に来なければいけないものが定まる。
あとはこの関係をトポロジカルソートすればよい。

int N,M,K;
string A[101010];
string B[101010];
int C[101010];
int tar[26][26][26][26];
vector<int> TB[101010];
int id[27][27][27][27];
int in[101010];
vector<int> ret;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(tar);
	MINUS(id);
	
	cin>>N>>M>>K;
	FOR(i,N) {
		cin>>A[i];
		A[i]+="aaaa";
		A[i]=A[i].substr(0,4);
		FORR(c,A[i]) {
			if(c=='_') c=26;
			else c-='a';
		}
		id[A[i][0]][A[i][1]][A[i][2]][A[i][3]]=i;
	}
	int mask;
	FOR(i,M) {
		cin>>B[i]>>C[i];
		C[i]--;
		B[i]+="aaaa";
		B[i]=B[i].substr(0,4);
		FORR(c,B[i]) c-='a';
		FOR(j,4) if(A[C[i]][j]!=26&&A[C[i]][j]!=B[i][j]) return _P("NO\n");
		if(tar[B[i][0]][B[i][1]][B[i][2]][B[i][3]]==-1) tar[B[i][0]][B[i][1]][B[i][2]][B[i][3]]=C[i];
		if(tar[B[i][0]][B[i][1]][B[i][2]][B[i][3]]!=C[i]) return _P("NO\n");
		FOR(mask,16) {
			int D[4];
			FOR(j,4) {
				if(mask&(1<<j)) D[j]=26;
				else D[j]=B[i][j];
			}
			x=id[D[0]][D[1]][D[2]][D[3]];
			if(x>=0&&x!=C[i]) {
				in[x]++;
				TB[C[i]].push_back(x);
			}
		}
	}
	queue<int> Q;
	FOR(i,N) if(in[i]==0) Q.push(i);
	while(Q.size()) {
		int cur=Q.front();
		Q.pop();
		ret.push_back(cur+1);
		FORR(r,TB[cur]) if(--in[r]==0) Q.push(r);
	}
	if(ret.size()==N) {
		cout<<"YES"<<endl;
		FORR(r,ret) cout<<r<<" ";
		cout<<endl;
	}
	else {
		cout<<"NO"<<endl;
	}
	
}

まとめ

考え方はさほど難しくないけど、実装はちょっとめんどい。