TopCoder SRM 658 Div1 Easy: OddEvenTree
SRM658に参加。Easy提出被撃墜で0pt。1292 → 1251 (-51)。だめだめだ。
問題
N個の頂点からなる木を作りたい。頂点間の距離の偶奇(EとO)を指定するので、それを満たすように木を作ることができるか、できるなら頂点同士のつながりを答えよ。
解法
頂点0を根とする。まず与えられた条件を満たす木を作ることができるか確認する。次の4つの条件をすべて満たしていれば、与えられた条件を満たす木を作ることができる。
(以下距離偶数をE、距離奇数をOと表します)
- 頂点iから頂点iへの距離(つまり自分自身への距離)がEである
- 頂点0との距離の偶奇がともにEまたはOの2点について、2点間の距離がEであること
- 頂点0との距離の偶奇が異なる2点について、2点間の距離がOであること
- 頂点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の条件を考えていなかったりといろいろとだめだった。