kanetaiの二次記憶装置

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

くじびき

くじびき(プログラミングコンテストチャレンジブックp8)

数字が書かれたn枚の紙切れが袋に入っている。紙切れに書かれた数字をk_1,k_2,\dots k_nとする。この袋から紙切れを取り出し、数字を見て袋に戻すということを4回行い、4回の紙切れの数字の和がmになる取り出し方が存在するならYes、存在しないならNoを出力する。
制約
1 \leq n \leq 1000
1 \leq m \leq 10^8
1 \leq k_i \leq 10^8

アルゴリズム

組み合わせの数はn^4 = 1000 ^4 = 10^{12}なので、4重ループをまわして、
 k_a + k_b + k_c + k_d = m
となるdを探す、戦略ではTLE。
式を移項して考えると、
k_d = m - k_a - k_b - k_c := x
となるdを探すと換言できる。
ソートしておいて、2分探索でxを探せば、オーダーは
O(n\log n)_{sort} + O(n^3 \log n)_{roop+search} = O(n^3 \log n)
となるが、これでもまだ計算量が多い。
そこで、
k_c + k_d = m - k_a - k_b
となるc,dを調べていると考える。あらかじめ、k_c + k_dを列挙しておき、それに対して2分探索すれば、
O(n^2 \log n)_{sort} + O(n^2 \log n)_{roop+search} = O(n^2 \log n)
で計算できる。

コード

import java.util.*;
public class lot {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new lot();
	}
	lot(){
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		int[] k = new int[n];
		for(int i = 0; i < n; i++) k[i] = scanner.nextInt();
		System.out.println( solve(n,m,k) );
	}
	String solve(int n, int m, int[] k){
		int[] kcd = new int[n*n]; //厳密にはn(n+1)/2で十分だが、簡単のため、n^2とおり列挙する
		for(int c = 0; c < n; c++)
			for(int d = 0; d < n; d++)
				kcd[c*n + d] = k[c] + k[d];
		Arrays.sort(kcd);
		
		boolean f = false;
		for(int a = 0; a < n; a++)
			for(int b = 0; b < n; b++)
				if(Arrays.binarySearch(kcd, m - k[a] - k[b]) >= 0)
					f =true;
		
		return f ? "Yes" : "No";
	}
}