roiti46's blog

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

TopCoder SRM 654 Div2 Med: OneEntrance

ちょっと考えた。

問題はこちら

問題

N(≦ 9)個の部屋があり部屋同士のつながりにより木構造を取っている。部屋sからN個の家具を順番に運び入れてすべての部屋に配置したいが、家具を置いた部屋を通ることはできないとする。家具の置き方は全部で何通りあるか答えよ。

解法

Nが小さいのですべての順列に対してシミュレーションすればいい。
問題では部屋同士のつながりしか与えられないので、まずそこから親子関係を作成する。あとは部屋に家具を入れる順番をすべて試せばいい。親部屋に運び入れるタイミングが子部屋に運び入れるタイミングより早くなければ家具の置き方としてありえる。

import itertools as it
def check(order, s, tree):
    N = len(order)
    for i in xrange(N):
        for j in tree[i]:
            if order[i] < order[j]: return False
    return True

def count(self, a, b, s):
    N = len(a) + 1
    tree = [[] for i in xrange(N)]
    que = [s]
    for i in xrange(N - 1):
        for j in xrange(N - 1):
            if a[j] == que[i] and b[j] not in que:
                tree[que[i]].append(b[j])
                que.append(b[j])
            if b[j] == que[i] and a[j] not in que:
                tree[que[i]].append(a[j])
                que.append(a[j])
    ans = 0
    for order in it.permutations(range(N), N):
        if check(order, s, tree):
            ans += 1
    return ans

まとめ

もっと簡単な親子関係の作り方がありそう。