結果
問題 | No.15 カタログショッピング |
ユーザー |
![]() |
提出日時 | 2015-08-14 19:32:53 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 897 ms / 5,000 ms |
コード長 | 5,160 bytes |
コンパイル時間 | 2,458 ms |
コンパイル使用メモリ | 84,588 KB |
実行使用メモリ | 127,452 KB |
最終ジャッジ日時 | 2024-07-18 09:29:31 |
合計ジャッジ時間 | 7,510 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 |
ソースコード
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int n1 = n / 2; int n2 = n - n1; int s = sc.nextInt(); int[] p1 = new int[n1]; int[] p2 = new int[n2]; for (int i = 0; i < n1; i++) { p1[i] = sc.nextInt(); } for (int i = 0; i < n2; i++) { p2[i] = sc.nextInt(); } TreeMap<Integer, ArrayList<TreeMap<Integer, Integer>>> fir = new TreeMap(); TreeMap<Integer, ArrayList<TreeMap<Integer, Integer>>> sec = new TreeMap(); int max1 = (int) Math.pow(2, p1.length); int max2 = (int) Math.pow(2, p2.length); for (int i = 1; i < max1; i++) { char[] bit = Integer.toBinaryString(i).toCharArray(); int sum = 0; TreeMap<Integer, Integer> tmpSet = new TreeMap(); for (int j = 0; j < bit.length; j++) { if (bit[j] == '1') { sum = sum + p1[bit.length - 1 - j]; tmpSet.put(bit.length - j, p1[bit.length - 1 - j]); } } ArrayList<TreeMap<Integer, Integer>> tmpList; if (fir.containsKey(sum)) { tmpList = fir.get(sum); } else { tmpList = new ArrayList(); fir.put(sum, tmpList); } tmpList.add(tmpSet); } for (int i = 1; i < max2; i++) { char[] bit = Integer.toBinaryString(i).toCharArray(); int sum = 0; TreeMap<Integer, Integer> tmpSet = new TreeMap(); for (int j = 0; j < bit.length; j++) { if (bit[j] == '1') { sum = sum + p2[bit.length - 1 - j]; tmpSet.put(bit.length - j + n1, p2[bit.length - 1 - j]); } } ArrayList<TreeMap<Integer, Integer>> tmpList; if (sec.containsKey(sum)) { tmpList = sec.get(sum); } else { tmpList = new ArrayList(); sec.put(sum, tmpList); } tmpList.add(tmpSet); } ArrayList<TreeMap<Integer, Integer>> merged = new ArrayList(); if (fir.containsKey(s)) { ArrayList<TreeMap<Integer, Integer>> set1 = fir.get(s); for (TreeMap<Integer, Integer> set11 : set1) { merged.add(set11); } } for (int key : fir.keySet()) { if (!sec.containsKey(s - key)) { continue; } ArrayList<TreeMap<Integer, Integer>> set1 = fir.get(key); ArrayList<TreeMap<Integer, Integer>> set2 = sec.get(s - key); for (int i = 0; i < set1.size(); i++) { TreeMap<Integer, Integer> merge = new TreeMap(); merger(merge, set1.get(i)); for (int j = 0; j < set2.size(); j++) { TreeMap<Integer, Integer> tmp = (TreeMap) merge.clone(); merger(tmp, set2.get(j)); merged.add(tmp); } } } if (sec.containsKey(s)) { ArrayList<TreeMap<Integer, Integer>> set2 = sec.get(s); for (int i = 0; i < set2.size(); i++) { merged.add(set2.get(i)); } } ArrayList<int[]> sorted = new ArrayList(); for (TreeMap<Integer, Integer> tmpSet : merged) { int[] tmp = new int[tmpSet.size()]; int i = 0; for (int key : tmpSet.keySet()) { tmp[i] = key; i++; } sorted.add(tmp); } sorted.sort(new C()); for (int[] tmpSet : sorted) { StringBuilder bf = new StringBuilder(); boolean first = true; for (int num : tmpSet) { if (first) { bf.append(num); System.out.print(num); first = false; } else { System.out.print(" " + num); } } System.out.println(); } } private static void merger( TreeMap<Integer, Integer> merge, TreeMap<Integer, Integer> source) { for (int key : source.keySet()) { merge.put(key, source.get(key)); } } public static class C implements Comparator<int[]> { //比較メソッド(データクラスを比較して-1, 0, 1を返すように記述する) public int compare(int[] a, int[] b) { for (int i = 0; i < a.length; i++) { int no1 = a[i]; int no2 = b[i]; //こうすると社員番号の昇順でソートされる if (no1 > no2) { return 1; } else if (no1 < no2) { return -1; } } return 0; } } }