唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

Google Code Jam Japan 2011決勝(A問題だけ)

長さが異なるK本のアンテナを等角度間隔に配置した時の面積の最大化.

方針

  1. すべてのアンテナの配置について計算するのは非効率.
  2. 大きな三角形から順に作っていけば,最大になるはず.
  3. ソートして大きいものから順にすでに配置されているアンテナの右側か左側に配置していく.

ソースコード

import math

with open("input.txt") as f:
  T = int(f.readline().strip())
  for i in xrange(T):
    K = int(f.readline().strip())
    A = 0
    E = map(int, f.readline().strip().split(" "))
    E.sort()
    t = []
    t.append([E.pop(), 0])
    while len(E) >= 1:
      A += t[0][0] * E[-1]
      t[0][1] += 1
      if t[0][1] >= 2:
        t.pop(0)
      t.append([E.pop(), 1])
    A += t[0][0] * t[1][0]
    print "Case #" + str(i + 1) + ": " + str(A * math.sin(2*math.pi / K) / 2)