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

kanetaiの二次記憶装置

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

三角形

三角形(プログラミングコンテストチャレンジブックp21)

n本の棒があり、棒iの長さはa_i。それらの棒から3本を選んでできるだけ周長の長い三角形を作ろうと考えている。最大の周囲はいくら?ただし、三角形が作れない場合は、0と答える。
制約
3 \leq n \leq 100
1 \leq a_i \leq 10^6

アルゴリズム

三角形を作ることができる必要十分条件(三角不等式)

最大辺長 < 他の2辺の長さの和

を使って、三角形が生成可能かを判定しながら、3重ループをまわすO(n^3)n = 100^3 = 10^6なので、これで十分だが、O(n log n)で解ける。


ソート済みの a_i
 b_1 \geq b_2 \geq \cdots \geq b_n
とすると求めるのは、 \max_{\{ i,j,k|1\leq i < j < k\leq n, b_i < b_j + b_k\} } b_i + b_j + b_k
iを決めたとして、j,kを [i+1, n] の範囲で探せばよい。
 b_i + b_j + b_kを最大化のみを考えると、j=i+1, j=i+2とすればよい。
そして、 b_i < b_{i+1} + b_{i+2}を満たさないのであれば、どんなj,kを選んでも b_i < b_j + a_kを満たすことはない。
従って、ソートしといて大きい方から連続する3辺について、三角不等式を満たすものを探せばよい
と思う...
 \max_{\{ i|b_i < b_{i+1} + b_{i+2} \} }  b_i + b_{i+1} + b_{i+2}

コード

import java.util.*;
public class triangle {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new triangle();
	}
	triangle(){
		int n = scanner.nextInt();
		Integer[] a = new Integer[n];
		for(int i = 0; i < n; i++)
			a[i] = scanner.nextInt();
		System.out.println( "solve 1 = " + solve1(n, a) );
		System.out.println( "solve 2 = " + solve2(n, a) );
	}
	
	// O(n^3)
	int solve1(int n, Integer[] a){
		int ans = 0;
		// i < j < k として、重複を避ける
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				for(int k = j+1; k < n; k++){
					int sum = a[i] + a[j] + a[k];
					int long_edge = Math.max(a[i], Math.max(a[j], a[k]));
					
					if(long_edge < sum - long_edge ) ans = Math.max(ans, sum);
				}
			}
		}
		return ans;
	}
	// O(n log n)
	int solve2(int n, Integer[] a){
		int ans = 0;
		Arrays.sort(a, new Comparator<Integer>(){
			@Override
			public int compare(Integer o1, Integer o2){ return o2.compareTo(o1); }
		});
		for(int i=0; i<n-2; ++i){
			if( a[i] < a[i+1] + a[i+2] ){
				ans = a[i] + a[i+1] + a[i+2];
				break;
			}
		}
		return ans;
	}
}