天下一プログラマーコンテスト2016 予選A : C - 山田山本問題

Bよりすんなり解けた。
http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualC_a

問題

アルファベット小文字で構成された、N個の文字列対(A[i],B[i])がある。
アルファベットの大小比較順を任意に変えられる場合、文字列の辞書順比較で常にA[i]＜B[i]となるようにしたい。

条件を満たす大小比較順が存在する場合、アルファベット26文字を小さい順に並べよ。
また複数の解が存在するなら(通常のアルファベットの大小順で)最小のものを求めよ。

解法

A[i]とB[i]が同じj文字のprefixを持つ場合、A[i][j]とB[i][j]の大小比較結果は前者のアルファベットが小とならなくてはならない。
N個の文字列対からそのような条件を集めよう。
その後、Warshall-Floyed等でその条件を推移させよう。
その結果、仮に「xはyより小さく、yはxより小さい」と言った矛盾する条件が登場した場合は条件を満たす比較順は存在しない。

それ以外の場合、以下の手順で１文字ずつアルファベットを選択して並べて行こう。

• 未選択のアルファベットの中に、自身より小さいアルファベットがないならそれを選択する。ただしそのようなものが複数存在するなら、元のアルファベット順で小さい方を選択する。

int N;
int ma[26][26];
string A,B;
int lef[26];

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>N;
	FOR(i,26) ma[i][i]=lef[i]=1;
	FOR(i,N) {
		cin>>A>>B;
		FOR(j,min(A.size(),B.size())) {
			if(A[j]!=B[j]) {
				ma[A[j]-'a'][B[j]-'a']=1;
				break;
			}
		}
		if(j==min(A.size(),B.size()) && A.size()>=B.size()) return _P("-1\n");
	}
	
	FOR(z,26) FOR(x,26) FOR(y,26) ma[x][y] |= ma[x][z] && ma[z][y];
	FOR(x,26) FOR(y,26) if(x!=y && ma[x][y] && ma[y][x]) return _P("-1\n");
	
	string R;
	while(R.size()<26) {
		FOR(x,26) if(lef[x]) {
			int ng=0;
			FOR(y,26) if(x!=y && lef[y] && ma[y][x]) ng=1;
			if(ng==0) {
				lef[x]=0;
				R += 'a'+x;
				break;
			}
		}
	}
	
	cout<<R<<endl;
}

まとめ

この問題どこかで出てそうだな。