Codeforces #290 Div2 C: Fox And Name

Dよりも難しく感じた。なぞのおまじないで通ってしまったのできちんと解法を理解できていない。

問題

問題はこちら

アルファベットからなる名前をN (≦ 100)個与えられる。あなたはアルファベットの順番を並び替えることにより、name[i] < name[j] (i < j) というふうに、上から名前が辞書順に並んでいるようにしたい。果たしてそのようなアルファベットの順番は実現可能か、可能ならそのうちの1つのアルファベット列を答える。

解法

name[i] と name[j] (i < j) について、用意したアルファベット列を用いて辞書順比較し、条件に合わなかったら合わなかった原因となった文字についてアルファベット列中の場所を変えるという作業を繰り返していけばいい。最後に、できたアルファベット列が条件をきちんと満たすかどうかを確認する。name[i] = aab, name[j] = aa などの場合はどうやっても条件をみたすことができないので注意する。

これで正解できるとおもいきや何度かWAとなってしまった。はっきりと原因を把握していないが、ijループを回している間に、小さなiについて条件を満たさなくなったのではと思い、適当にloopを増やしたら通ってしまった。なぜ2回で十分なのかわかっていないので、そこは目をつぶってもらいたいです。

def check(name0,name1,alpha):
    for i in xrange(min(len(name0),len(name1))):
        if alpha.index(name0[i]) < alpha.index(name1[i]): return -1
        if alpha.index(name0[i]) > alpha.index(name1[i]): return i
    return -1 if len(name0) <= len(name1) else -2

alpha = list("abcdefghijklmnopqrstuvwxyz")
N = int(raw_input())
name = [raw_input() for i in xrange(N)]

for loop in xrange(2):
    for i in xrange(N):
        for j in xrange(i+1,N):
            p = check(name[i],name[j],alpha)
            if p > -1:
                a,b = alpha.index(name[i][p]),alpha.index(name[j][p])
                char = alpha.pop(b)
                alpha.insert(a,char)
            elif p == -2:
                print "Impossible"
                exit()
ans = True
for i in xrange(N):
    for j in xrange(i+1,N):
        if check(name[i],name[j],alpha) > -1:
            ans = False
            break
    if not ans: break
print "".join(alpha) if ans else "Impossible"