TopCoder SRM 658 Div1 x-- 1266->1232

0時という健康的な時間だったので参加
残念ながら1問も解けず

344位, 0.0点, +0/-0 challenge
Volatility: 255->241

250: OddEvenTree

グラフのすべてのノード間のペアについて、距離が偶数か奇数かが与えられる
与えられる距離の偶奇を満たすある木の辺を出力する(木はすべてのノードを含む)
満たす木が作れない場合には-1を出力

与えられた距離の関係が木としておかしいものでなければ、0番のノードに繋げられるだけ奇数距離のノードを繋いで、適当な奇数距離のノードに残りの偶数距離のノードを繋げば条件を満たす(奇数距離で繋がっているノードを別の奇数距離のノードに繋ぎかえても偶数奇数の関係は変わらない。偶数番目のノードについても同様)

距離の関係が正しいかどうかの判定が間違っていて本番では不正解

下記をチェックすればよいはず

• 自分自身への距離が偶数になっているか(自分自身への距離は0)
• 距離は対称になっているか(ノードiからノードjへの距離と、ノードjからノードiまでの距離が等しいか)
• 各ノードについて、奇数距離のノードが1つ以上存在するか
• 推移関係に矛盾がないか(ノードiからノードjへの距離、ノードiからノードkとノードkからノードjまでの距離の間の関係が正しいか)
  • 本番ではこの条件を忘れたorz

# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect

class OddEvenTree:
    def getTree(self, x):
        L = len(x)
        
        for i in xrange(L):
            if x[i][i] != 'E':
                return (-1,)
            countO = 0
            for j in xrange(L):
                if x[i][j] != x[j][i]:
                    return (-1,)
                countO += x[i][j] == 'O'
            if countO == 0:
                return (-1,)
        for i in xrange(L):
            for j in xrange(L):
                for k in xrange(L):
                    if (x[i][j] == 'O' and x[i][k] == x[k][j]) or (x[i][j] == 'E' and x[i][k] != x[k][j]):
                        return (-1,)
        result = []
        for i in xrange(1, L):
            if x[0][i] == 'O':
                result.append(0)
                result.append(i)
        
        idxO = result[1]
        for i in xrange(1, L):
            if x[0][i] == 'E':
                result.append(idxO)
                result.append(i)
        return tuple(result)