くじびき
くじびき(プログラミングコンテストチャレンジブックp8)
数字が書かれたn枚の紙切れが袋に入っている。紙切れに書かれた数字をとする。この袋から紙切れを取り出し、数字を見て袋に戻すということを4回行い、4回の紙切れの数字の和がmになる取り出し方が存在するならYes、存在しないならNoを出力する。
制約
アルゴリズム
組み合わせの数はなので、4重ループをまわして、
となるdを探す、戦略ではTLE。
式を移項して考えると、
となるdを探すと換言できる。
ソートしておいて、2分探索でxを探せば、オーダーは
となるが、これでもまだ計算量が多い。
そこで、
となるc,dを調べていると考える。あらかじめ、を列挙しておき、それに対して2分探索すれば、
で計算できる。
コード
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"; } }