TopCoder SRM 638 Div1 x-- 1283->1284

156th, 0.00pts, +0/-0 challenge
Volatility: 512->462

いつもどおりDiv1 Easyが解けず。
Challengeいけそうな気がしたけど、毎回このパターンでマイナスの点になっているので我慢した

300: ShadowSculpture

立方体をいずれかの面がくっつくようにつなげていって、与えられたXY、YZ、ZX平面の影の形を満たす立体を作れるかどうかを判定する

一度提出してから間違いに気づいて提出し直そうと思ったけど間に合わず
Practiceで通そうとしたら、考えなおした後の方針は合っていたけど、実装とコーナーケースの扱いがボロボロで苦戦しました

やったことは、影の形的に置ける場所にすべて立方体を置く
面同士がくっついていない場合があるので、Union-Findで連結成分を求めてそのうち最大のまとまりが影の条件を満たすかどうかで判定する(連結成分を求めるのは深さ優先探索でもよいような)

ちなみにUnion-Findの説明は以下のサイトがわかりやすかったです

• Algorithms with Python / Union-Find

Practiceで通したコード(汚い)

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

class UnionFind:
    def __init__(self, size):
        self.table = [-1] * size

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

class ShadowSculpture:
    def possible(self, XY, YZ, ZX):
        print
        n = len(XY)
        
        field = [[[0 for x in xrange(n + 2)] for y in xrange(n + 2)] for z in xrange(n + 2)]
        for x in xrange(n):
            for y in xrange(n):
                for z in xrange(n):
                    if XY[x][y] == 'Y' and YZ[y][z] == 'Y' and ZX[z][x] == 'Y':
                        field[x + 1][y + 1][z + 1] = 1
        uf = UnionFind(n**3)
        for x in xrange(n):
            for y in xrange(n):
                for z in xrange(n):
                    for i in [-1, 0, 1]:
                        for j in [-1, 0, 1]:
                            for k in [-1, 0, 1]:
                                if field[x + 1][y + 1][z + 1] == 1 and field[x + 1 + i][y + 1 + j][z + 1 + k] == 1 and 0 < abs(i) + abs(j) + abs(k) < 2:
                                    uf.union(x + n * y + n * n * z, (x + i) + n * (y + j) + n * n * (z + k))
        counter = collections.Counter()
        for x in xrange(n):
            for y in xrange(n):
                for z in xrange(n):
                    if field[x + 1][y + 1][z + 1] == 1:
                        counter[uf.find(x + n * y + n * n * z)] += 1
        key = counter.most_common(1)[0][0] if len(counter.most_common(1)) > 0 else -1
        shadowXY = [['N' for x in xrange(n)] for y in xrange(n)]
        shadowYZ = [['N' for x in xrange(n)] for y in xrange(n)]
        shadowZX = [['N' for x in xrange(n)] for y in xrange(n)]
        for x in xrange(n):
            for y in xrange(n):
                for z in xrange(n):
                    if field[x + 1][y + 1][z + 1] == 1 and uf.find(x + n * y + n * n * z) == key:
                        shadowXY[x][y] = 'Y'
                        shadowYZ[y][z] = 'Y'
                        shadowZX[z][x] = 'Y'
        for x in xrange(n):
            for y in xrange(n):
                if shadowXY[x][y] != XY[x][y] or shadowYZ[x][y] != YZ[x][y] or shadowZX[x][y] != ZX[x][y]:
                    return 'Impossible'
        return "Possible"