CodeIQ：巡回サンタクロース問題

問題の概要

次のようにパラメータが入力されます。

1行目はパラメータの入力数です。
2行目以降がパラメータです。
この例だとサンタクロースはA~Dの家にプレゼントを配る必要があり、それぞれの家に配る荷物の重さはA:2、B:3、C:1、D:4となります。 また各家の距離は2つの家に配るプレゼントの重さの積に等しいとなっています。例えばA-Bは距離6、A-Cは距離2、B-Dは距離12です。
サンタクロースは（まだ配っていない荷物の重さの合計）×（家と家の間の距離）だけエネルギーを消費します。
エネルギーを最小にする経路を求め、その時に消費するエネルギーを出力せよ、と言う問題です。

私のプログラム

Pythonで解答しています。

import fileinput

#==============================================================================
#	探索中の経路を管理するクラス
#------------------------------------------------------------------------------
class Candidate:
	def __init__(self, path, less):
		self.Path = path		# 通過済みの場所
		self.Less = less		# まだ行ってない場所

	def __str__(self):
		return str(self.Path) + str(self.Less)

	#	可能性のある経路のリストを返す
	#	閾値を超えてしまう経路は切り捨てる
	def getNextCandidates(self, th):
		ret = []
		for i in self.Less:
			p = self.Path[:]
			l = self.Less[:]

			p.append(i)
			l.remove(i)

			if th >= calcCost(p):
				c = Candidate(p, l)
				ret.append(c)

		return ret

	# 通過済みの場所にかかるコストを計算する
	def calcPathCost(self):
		return calcCost(self.Path)

#==============================================================================
#	枝刈りの基準となる並びを生成する
#	要素を大きい方からMax1,Max2,Max3,...,Min3,Min2,Min1とした場合、
#		Max1, Min1,Max2,Min2,...
#	の並びは結構いい線を行くのでこれを基準にする
#------------------------------------------------------------------------------
def getThresholdList(lst):
	l = lst[:]
	a = []
	even = True

	while len(l):
		if even:
			n = max(l)
		else:
			n = min(l)

		a.append(n)
		l.remove(n)
		even = not even

	return a

#==============================================================================
#	リストの経路の移動にかかるコストを計算する
#------------------------------------------------------------------------------
def calcCost(l):
	total = 0
	pos = 1
	w = Weight

	for i in l[1:]:
		w -= l[pos-1]
		total += w * l[pos-1] * l[pos]
		pos += 1

	return total

#==============================================================================
#	次の候補リストを作成する
#	Thresholdを超えたコストのかかる経路は無視する
#------------------------------------------------------------------------------
def getNewCandidates(lst, th):
	new_lst = []

	for i in lst:
		cost = i.calcPathCost()
		new_lst += i.getNextCandidates(th)

	return new_lst

#==============================================================================
#	最小コストの経路を返す
#------------------------------------------------------------------------------
def getMin(lst, th):
	mi = th	# 最小コスト
	pos = -1

	for i, c in enumerate(lst):
		cost = c.calcPathCost()
		if cost <= mi:
			mi = cost
			pos = i

	return lst[pos]

def printResults(lst):
	for i in lst:
		c = i.calcPathCost()
		print(str(i) + " -> " +str(c))

#==============================================================================
# main
#------------------------------------------------------------------------------
LineNo = 0		# 読み込んだ行数
Presents = []	# 読み込んだ値のリスト
Threshold = 0	# 閾値
Weight = 0		# 全重量

for line in fileinput.input():
	if not line.strip():
		continue

	if LineNo:
		i = int(line.strip())
		Presents.append(i)
		Weight += i
	LineNo += 1

MaxMin = getThresholdList(Presents)
Threshold = calcCost(MaxMin)

# 少なくとも要素の半分まではMax1, Min1, Max2, Min2, ...の順で並ぶらしい
Mid = len(MaxMin) // 2
new_cand = [Candidate(MaxMin[:Mid], MaxMin[Mid:])]

for i in range(len(MaxMin) - Mid):
	new_cand = getNewCandidates(new_cand, Threshold)

mi = getMin(new_cand, Threshold)
print(str(mi.calcPathCost()))

解説

この問題は一度実行時間オーバーで失敗しています。
最大の入力数の場合で3秒を切っていたので大丈夫か？ と思っていましたがダメでした。

それでは具体的にプログラムの説明をします。

雑感

結局これでテストケースをパスしました。
多分、このプログラムを使って経路数20くらいまでシミュレートすると法則からもっと高速なプログラムを作れると思いますが、ちょっとそこまでする根性がなくここで終了としました。