kmjp's blog

競技プログラミング参加記です

TopCoder SRM 705 Div1 Easy AlphabetOrderDiv1、Div2 Medium AlphabetOrderDiv2

うーん、朝回なので不参加だったけど、あっさり解けたので出ておきたかった…。
https://community.topcoder.com/stat?c=problem_statement&pm=10529
https://community.topcoder.com/stat?c=problem_statement&pm=14474

問題

この国では、文字としてアルファベット小文字26種を用いるが、その辞書順大小は不明である。
ここでいくつかの単語が与えられる。
各単語内の文字の並びが辞書順となるようなアルファベット26種の大小の組み合わせは存在するか判定せよ。

解法

各文字列内の2文字を比較することで、2文字間の大小が定まる。
あとはWarshall-Floyed法などで全文字間の大小を求めよう。

最後に矛盾が生じないか判定する。
すなわち異なる2文字P,Qに対しP<QかつP>Qとなる場合は条件を満たす組み合わせは存在しない。

class AlphabetOrderDiv1 {
	public:
	string isOrdered(vector <string> words) {
		int mat[26][26]={};
		int i,x,y,z;
		FOR(i,26) mat[i][i]=1;
		
		FORR(w,words) FOR(y,w.size()) FOR(x,y) mat[w[x]-'a'][w[y]-'a']=1;
		FOR(z,26) FOR(x,26) FOR(y,26) mat[x][y] |= mat[x][z] & mat[z][y];
		FOR(y,26) FOR(x,y) if(mat[x][y] && mat[y][x]) return "Impossible";
		return "Possible";
	}
}

まとめ

今回珍しくDiv1 EasyとDiv2 Mediumが同じ問題で、テストケースのみ後者の方が豊富という変わった構成。