TopCoder SRM 737 Div1 Medium GroupTheNumbers

SRMで初めてPython使った。
http://community.topcoder.com/stat?c=problem_statement&pm=15078

問題

いくつかの整数が与えられる。
これらをいくつかのグループに分けたのち、グループ内の要素の積を取ったものの総和として得られるもののうち最大値を求めよ。

解法

まず、値を0,1,-1,2以上の正の数,-2以下の負の数、の５通りに分類しよう。
基本的に積の値がでかくなるよう値を掛けまくるのが良いが、0や1は和に回した方がいいこともあるので注意。

• 負の数が偶数個の場合
  • 全要素を掛けても負にはならないので、基本的には符号を気にせずガンガン全要素を掛けるのがよい。
  • ただし、0,1は掛けてもいいことはないので和に回し掛けない。また、-1は2つペアにできれば2つずつかけて1解に寄与させる。
• 負の数が奇数個の場合
  • 愚直に負の数を全部掛けると結果が負になるので、絶対値が最小の１要素だけ省くことにしよう。
  • 省いた要素は、0がほかにあるならそれと掛け合わせる。なければしょうがないので負の値を解に加算する。
  • それを除けば偶数の場合と同じ。

結果に多倍長演算が求められるので注意しよう。

class GroupTheNumbers():
	def calculate(self,a):
		n0 = nm = 0
		p = []
		m = []
		
		ret = 0
		for v in a:
			if v==0:
				n0 += 1
			elif v == 1:
				ret += 1
			elif v>0:
				p.append(v)
			else:
				m.append(v)
		if nm:
			m.append(-1)
		
		m.sort()
		if len(m)%2==1:
			if n0==0:
				ret += m[-1]
			m = m[:-1]
		while len(m) and m[-1]==-1 and m[-2]==-1:
			ret += 1
			m.pop()
			m.pop()
			

		if len(p)+len(m):
			b = 1
			for v in p:
				b *= v
			for v in m:
				b *= v
			ret += b
		rets = str(ret)
		if len(rets)>203:
			rets = rets[0:100] + "..." + rets[-100:]
		
		return rets

まとめ

すでにどっかで出てそう。
これmod 10^7とかじゃダメだったのかなぁ。