Code Jam Japan 2011 決勝 問題A. アンテナ修復

Code Jam Japan 2011の決勝の問題Aを解いてみた。

■ 考え方

・最大になる組み合わせを総当たりで計算した場合、間違いなくLargeが解けないので、何らかの法則を見つける必要がある

・まずは三角形の面積について、基本的な計算方法を明確にする。隣り合うエレメントが作る三角形の面積は、各エレメントの長さをa、bとすると、次のようになる

　a * b * sin(2π/K) / 2

・よって、エレメントの並び順が（X1, X2,・・, Xk）の場合、三角形の面積の合計は、次のようになる

　(X1 * X2 + X2 * X3 + ・・ + Xk * X1) * sin(2π/K) / 2

つまり、(X1 * X2 + X2 * X3 + ・・ + Xk * X1) の部分が最大になる並べ方を求めれば、それでPを求めることが出来る

・上記の値が最大になるのは、X1～Xkを降順にソートした結果をY1～Ykとすると、Y1を基準にY2以降を左右に順に並べていけばよいことになる

　・・・, Y7, Y5, Y3, Y1, Y2, Y4, Y6, ・・・

■ プログラム

use Math::Trig qw( pi );
sub solve{
my @list = @{$_[0]};
my $size = @list;
my @sorted = sort {$b <=> $a} @list;
my @list2 = ();
$element_list[0] = $sorted[0];
my $x = 1;
my $y = $size - 1;
for(my $i = 1; $i < $size; $i++){
if($i % 2 == 0){
$element_list[$y] = $sorted[$i];
$y--;
}else{
$element_list[$x] = $sorted[$i];
$x++;
}
}
my $result = $element_list[0] * $element_list[$size - 1];
for(my $i = 1; $i < $size; $i++){
$result += $element_list[$i] * $element_list[$i - 1];
}
return ($result / 2 * sin(2*pi()/$size));
}
$count = 0;
while(<>){
chop;
if($count>0){
my $size = $_;
$_ = <>;
chop;
my @list = split(/ /, $_);
printf "Case #%d: %.9f\n", $count, solve(\@list);
}
$count++;
}