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
まとめ
もっと簡単な親子関係の作り方がありそう。