読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

問題A. アンテナ修復(Google Code Jam Japan 2011 Final)

久しぶりにやったお。

問題A. アンテナ修復

エレメント(線分)の個数Kとエレメントの長さE1〜EKが与えられる。

・すべてのエレメントが同一平面上にある
・すべてのエレメントの + 極が同じ位置にある。これを接続点と呼ぶ
・エレメント同士が重なるのは接続点のみ
・隣り合うエレメントがなす角度はすべて 360/K 度である

隣り合うエレメントの - 極の位置 2 点と接続点で作られる三角形の面積を隣り合うエレメントの組み合わせすべてについて足しあわせた値がアンテナの強度となる。

アンテナの強度を最大化する並べ方での強度を出力せよ。

アルゴリズム

 E_1 \rightarrow E_2 \rightarrow \cdots \rightarrow E_K \rightarrow E_1
と円形に並べたときのアンテナ強度は、
 \frac{1}{2}(E_1E_2 + E_2E_3 + \cdots + E_{K-1}E_K + E_KE_1)\sin (\frac{2\Pi }{K})
となる。
並び方を変えてこれを最大化したい場合、
積和を最大化して最後に1/2とsinをかければいい。
大きいもの同士を掛けていくと、積和が最大になりそう。

ほしいのは、並べ方ではなく、アンテナ強度だけなので、ソートして
 E_1 \leq E_2 \leq \cdots \leq E_K
となった状態で考える。
巡回することに注意して、
 \cdots \leftarrow E_{K-4} \leftarrow E_{K-2} \leftarrow E_K \rightarrow E_{K-1} \rightarrow E_{K-3} \rightarrow \cdots
のように E_kから左右に配置していけば強度最大。

コード

javaってプリミティブ型の配列の降順ソートは用意されてないのかな?
C++ならプレディケートgreaterがあるけど...
 E_1 \rightarrow E[ 0]
※E[0]から小さい順に左右に配置しても同じなのでそうしてる。
※E[0]とE[1], E[k-1]とE[K-2]の接続を先に計算している。

import java.util.*;
import java.lang.*;

public class CodeJamJapan2011final_A {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new CodeJamJapan2011final_A();
	}
	CodeJamJapan2011final_A(){
		int T = scanner.nextInt();
		for(int i=0; i<T; ++i){
			int K = scanner.nextInt();
			int[] E = new int[K];
			for(int j=0; j<K; ++j)
				E[j] = scanner.nextInt();
			
			System.out.println( "Case #" + (i+1) + ": " +solve(K,E) );
		}
	}
	double solve(int K, int[] E){
		Arrays.sort(E);
		int res = E[0]*E[1] + E[K-1]*E[K-2];
		for(int i=0; i+2 < K; i++)
			res += (E[i]*E[i+2]);
		return Math.sin( 2* Math.PI / K ) /2 * res;
	}

}