roiti46's blog

主に競プロ問題の解説を載せてます

TopCoder SRM 658 Div1 Easy: OddEvenTree

SRM658に参加。Easy提出被撃墜で0pt。1292 → 1251 (-51)。だめだめだ。

問題

N個の頂点からなる木を作りたい。頂点間の距離の偶奇(EとO)を指定するので、それを満たすように木を作ることができるか、できるなら頂点同士のつながりを答えよ。

解法

頂点0を根とする。まず与えられた条件を満たす木を作ることができるか確認する。次の4つの条件をすべて満たしていれば、与えられた条件を満たす木を作ることができる。
(以下距離偶数をE、距離奇数をOと表します)

  1. 頂点iから頂点iへの距離(つまり自分自身への距離)がEである
  2. 頂点0との距離の偶奇がともにEまたはOの2点について、2点間の距離がEであること
  3. 頂点0との距離の偶奇が異なる2点について、2点間の距離がOであること
  4. 頂点0との距離の偶奇がOの点がある

2と3については、頂点0を経由したとしても2点間の距離の偶奇は変わらないことを利用している。

グラフの構築は貪欲的にできる。
まず頂点0との距離の偶奇がOのすべての点を頂点0と結ぶ。
そのあと頂点0と結んだどれか1つの点と頂点0との距離の偶奇がEのすべての点を結ぶ。
2と3の条件を確かめているので、この方法で与えられた条件を満たす木を構築することができる。

def getTree(self, x):
    N = len(x)
    for i in xrange(N):
        for j in xrange(N):
            if x[0][i] != x[0][j] :
                if not (x[i][j] == x[j][i] == "O"): return [-1]
            else:
                if not (x[i][j] == x[j][i] == "E"): return [-1]
                
    ans = []
    for i in xrange(1, N):
        if x[0][i] == "O":
            ans.append(0)
            ans.append(i)
    if len(ans) == 0: return [-1]
    o = ans[-1]
    for i in xrange(1, N):
        if x[0][i] == "E":
            ans.append(o)
            ans.append(i)
    return ans

まとめ

append(i)をappend(1)と書き間違えていたり、4の条件を考えていなかったりといろいろとだめだった。