問題 : http://nabetani.sakura.ne.jp/hena/orde11tredis/
実装リンク集 : http://qiita.com/Nabetani/items/10b2ccc28301e44e09e6
ツリー内のノードをクラスにしました。
同じ値のノードがいくつも登場するのでキャッシュあり版も作ってみました。
- 子ノードに２つの距離を聞いてみる。ない場合もある
- 自ノードを挟んで２つの距離を調べる。ない場合もある。
- 子ノード内の距離と自ノードを挟んだ距離の短い方を選ぶ。ルートノードでは必ず見つかる。
E11.py(キャッシュなし版)
class Node:
def __init__(self, number):
self.number = number
self.children = [Node(i + 1)
for i in range(2, number // 2 + 1)
if number % i == 0]
def distances(self, number):
if number > self.number: return []
if number == self.number: return [0]
return [distance + 1
for child in self.children
for distance in child.distances(number)]
def distances_between(self, a, b):
distances_in_children = [distance
for child in self.children
for distance in child.distances_between(a, b)]
da, db = self.distances(a), self.distances(b)
distance_across_self = [min(da) + min(db)] if da and db else []
return distances_in_children + distance_across_self
def distance_between(self, a, b):
return min(self.distances_between(a, b))
def solve(data):
root, ab = data.split(':')
a, b = map(int, ab.split(','))
return str(Node(int(root)).distance_between(a, b))
def test(no, data, correct):
answer = solve(data)
result = "OK" if answer == correct else "NG"
print result, '%2d' % no, data, correct, '->', answer
if __name__ == '__main__':
test( 0, "50:6,3", "1" );
test( 1, "98:5,11", "4" );
test( 2, "1000:33,20", "7" );
test( 3, "514:9,18", "8" );
test( 4, "961:5,4", "3" );
test( 5, "1369:1369,3", "2" );
test( 6, "258:16,12", "5" );
test( 7, "235:13,3", "2" );
test( 8, "1096:19,17", "8" );
test( 9, "847:7,17", "6" );
test(10, "1932:3,5", "2" );
test(11, "2491:4,8", "3" );
test(12, "840:421,36", "2" );
test(13, "1430:37,111", "3" );
test(14, "496:17,9", "2" );
test(15, "891:6,10", "1" );
test(16, "1560:196,21", "2" );
test(17, "516:20,12", "5" );
test(18, "696:30,59", "2" );
test(19, "1760:5,441", "2" );
test(20, "1736:11,26", "5" );
test(21, "1518:17,34", "4" );
test(22, "806:63,16", "5" );
test(23, "1920:3,97", "2" );
test(24, "1150:13,22", "4" );
test(25, "920:116,5", "1" );
test(26, "2016:7,337", "2" );
test(27, "408:9,25", "2" );
test(28, "735:36,8", "2" );
test(29, "470:5,31", "2" );
test(30, "2100:12,351", "3" );
test(31, "870:36,10", "1" );
test(32, "1512:253,13", "2" );
test(33, "697:12,15", "3" );
test(34, "1224:5,14", "2" );
test(35, "986:125,17", "3" );
test(36, "864:12,13", "3" );
test(37, "500:21,51", "2" );
test(38, "819:33,21", "4" );
test(39, "594:55,3", "2" );
test(40, "638:17,24", "3" );
E11.py(キャッシュあり版)
class Node:
cache = {}
@staticmethod
def get(number):
if number in Node.cache: return Node.cache[number]
Node.cache[number] = node = Node(number)
return node
def __init__(self, number):
self.number = number
self.children = [Node.get(i + 1)
for i in range(2, number // 2 + 1)
if number % i == 0]
def distances(self, number):
if number > self.number: return []
if number == self.number: return [0]
return [distance + 1
for child in self.children
for distance in child.distances(number)]
def distances_between(self, a, b):
distances_in_children = [distance
for child in self.children
for distance in child.distances_between(a, b)]
da, db = self.distances(a), self.distances(b)
distance_across_self = [min(da) + min(db)] if da and db else []
return distances_in_children + distance_across_self
def distance_between(self, a, b):
return min(self.distances_between(a, b))
def solve(data):
number, ab = data.split(':')
a, b = map(int, ab.split(','))
return str(Node.get(int(number)).distance_between(a, b))
def test(no, data, correct):
answer = solve(data)
result = "OK" if answer == correct else "NG"
print result, '%2d' % no, data, correct, '->', answer
if __name__ == '__main__':
test( 0, "50:6,3", "1" );
test( 1, "98:5,11", "4" );
test( 2, "1000:33,20", "7" );
test( 3, "514:9,18", "8" );
test( 4, "961:5,4", "3" );
test( 5, "1369:1369,3", "2" );
test( 6, "258:16,12", "5" );
test( 7, "235:13,3", "2" );
test( 8, "1096:19,17", "8" );
test( 9, "847:7,17", "6" );
test(10, "1932:3,5", "2" );
test(11, "2491:4,8", "3" );
test(12, "840:421,36", "2" );
test(13, "1430:37,111", "3" );
test(14, "496:17,9", "2" );
test(15, "891:6,10", "1" );
test(16, "1560:196,21", "2" );
test(17, "516:20,12", "5" );
test(18, "696:30,59", "2" );
test(19, "1760:5,441", "2" );
test(20, "1736:11,26", "5" );
test(21, "1518:17,34", "4" );
test(22, "806:63,16", "5" );
test(23, "1920:3,97", "2" );
test(24, "1150:13,22", "4" );
test(25, "920:116,5", "1" );
test(26, "2016:7,337", "2" );
test(27, "408:9,25", "2" );
test(28, "735:36,8", "2" );
test(29, "470:5,31", "2" );
test(30, "2100:12,351", "3" );
test(31, "870:36,10", "1" );
test(32, "1512:253,13", "2" );
test(33, "697:12,15", "3" );
test(34, "1224:5,14", "2" );
test(35, "986:125,17", "3" );
test(36, "864:12,13", "3" );
test(37, "500:21,51", "2" );
test(38, "819:33,21", "4" );
test(39, "594:55,3", "2" );
test(40, "638:17,24", "3" );
実行結果
$ python E11.py
OK 0 50:6,3 1 -> 1
OK 1 98:5,11 4 -> 4
OK 2 1000:33,20 7 -> 7
OK 3 514:9,18 8 -> 8
OK 4 961:5,4 3 -> 3
OK 5 1369:1369,3 2 -> 2
OK 6 258:16,12 5 -> 5
OK 7 235:13,3 2 -> 2
OK 8 1096:19,17 8 -> 8
OK 9 847:7,17 6 -> 6
OK 10 1932:3,5 2 -> 2
OK 11 2491:4,8 3 -> 3
OK 12 840:421,36 2 -> 2
OK 13 1430:37,111 3 -> 3
OK 14 496:17,9 2 -> 2
OK 15 891:6,10 1 -> 1
OK 16 1560:196,21 2 -> 2
OK 17 516:20,12 5 -> 5
OK 18 696:30,59 2 -> 2
OK 19 1760:5,441 2 -> 2
OK 20 1736:11,26 5 -> 5
OK 21 1518:17,34 4 -> 4
OK 22 806:63,16 5 -> 5
OK 23 1920:3,97 2 -> 2
OK 24 1150:13,22 4 -> 4
OK 25 920:116,5 1 -> 1
OK 26 2016:7,337 2 -> 2
OK 27 408:9,25 2 -> 2
OK 28 735:36,8 2 -> 2
OK 29 470:5,31 2 -> 2
OK 30 2100:12,351 3 -> 3
OK 31 870:36,10 1 -> 1
OK 32 1512:253,13 2 -> 2
OK 33 697:12,15 3 -> 3
OK 34 1224:5,14 2 -> 2
OK 35 986:125,17 3 -> 3
OK 36 864:12,13 3 -> 3
OK 37 500:21,51 2 -> 2
OK 38 819:33,21 4 -> 4
OK 39 594:55,3 2 -> 2
OK 40 638:17,24 3 -> 3