うーん、朝回なので不参加だったけど、あっさり解けたので出ておきたかった…。
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が同じ問題で、テストケースのみ後者の方が豊富という変わった構成。