こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
Java: paiza事務局作成コード Vol.4 O(DN)
通過テストケース数:3
実行時間(テストケース1):0.08秒
実行時間(テストケース2):0.10秒
実行時間(テストケース3):0.23秒
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { private static int search(final int n, final int[] p) { int price = 0; int max = 0; int i = 0, j = p.length - 1; while (true) { price = p[i] + p[j]; if (price == n) { max = n; break; } else if (price < n && price > max) { max = price; } if (price < n) { i++; } else if (price > n) { j--; } if (i >= j) { break; } } return max; } public static void main(String[] args) { final int N; final int D; final int[] p; final int[] m; try (BufferedReader br = new BufferedReader(new InputStreamReader( System.in))) { String[] line_nd = br.readLine().split(" "); N = Integer.valueOf(line_nd[0]); D = Integer.valueOf(line_nd[1]); p = new int[N]; for (int i = 0; i < N; i++) { p[i] = Integer.valueOf(br.readLine()); } Arrays.sort(p); m = new int[D]; for (int i = 0; i < D; i++) { m[i] = Integer.valueOf(br.readLine()); } for (int v : m) { System.out.println(search(v, p)); } } catch (Exception e) { e.printStackTrace(); } } }
Java: paiza事務局作成コード Vol.3 O(DNlogN)
通過テストケース数:3
実行時間(テストケース1):0.09秒
実行時間(テストケース2):0.26秒
実行時間(テストケース3):5.58秒
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { private static int search(final int n, final int[] p) { int max = 0; int mid = 0; int tmp = 0; for (int i = 0; i < p.length; i++) { int r = n - p[i]; int lb = 0; int ub = p.length; while (ub - lb != 1) { mid = (ub + lb) / 2; if (p[mid] <= r) { lb = mid; } else { ub = mid; } } ub -= 1; if (i >= ub) continue; if (p[ub] > r) continue; tmp = p[i] + p[ub]; if (tmp <= n && max < tmp) { max = tmp; } } return max; } public static void main(String[] args) { final int N; final int D; final int[] p; final int[] m; try (BufferedReader br = new BufferedReader(new InputStreamReader( System.in))) { String[] line_nd = br.readLine().split(" "); N = Integer.valueOf(line_nd[0]); D = Integer.valueOf(line_nd[1]); p = new int[N]; for (int i = 0; i < N; i++) { p[i] = Integer.parseInt(br.readLine()); } Arrays.sort(p); m = new int[D]; for (int i = 0; i < D; i++) { m[i] = Integer.parseInt(br.readLine()); } for (int v : m) { System.out.println(search(v, p)); } } catch (Exception e) { e.printStackTrace(); } } }
Java: paiza事務局作成コード Vol.2 O(DN^2)
通過テストケース数:2
実行時間(テストケース1):0.10秒
実行時間(テストケース2):3.41秒
実行時間(テストケース3):--
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; public class Main { private static int search(final int n, final int[] p) { int max = 0; for (int i = 0; i < p.length; i++) { for (int j = i + 1; j < p.length; j++) { final int price = p[i] + p[j]; if (price > n) { break; } else if (price > max) { max = price; } } } return max; } public static void main(String[] args) { final int N; final int D; final int[] p; final int[] m; try (BufferedReader br = new BufferedReader(new InputStreamReader( System.in))) { String[] line_nd = br.readLine().split(" "); N = Integer.valueOf(line_nd[0]); D = Integer.valueOf(line_nd[1]); p = new int[N]; for (int i = 0; i < N; i++) { p[i] = Integer.parseInt(br.readLine()); } Arrays.sort(p); m = new int[D]; for (int i = 0; i < D; i++) { m[i] = Integer.parseInt(br.readLine()); } for (int v : m) { System.out.println(search(v, p)); } } catch (Exception e) { e.printStackTrace(); } } }
Java: paiza事務局作成コード Vol.1 O(DN^2)
通過テストケース数:1
実行時間(テストケース1):0.15秒
実行時間(テストケース2):--
実行時間(テストケース3):--
import java.io.BufferedReader; import java.io.InputStreamReader; public class Main { private static int search(final int n, final int[] p) { int max = 0; for (int i = 0; i < p.length; i++) { for (int j = i + 1; j < p.length; j++) { final int price = p[i] + p[j]; if (price > max && price <= n) { max = price; } } } return max; } public static void main(String[] args) { final int N; final int D; final int[] p; final int[] m; try (BufferedReader br = new BufferedReader(new InputStreamReader( System.in))) { String[] line_ND = br.readLine().split(" "); N = Integer.valueOf(line_ND[0]); D = Integer.valueOf(line_ND[1]); p = new int[N]; for (int i = 0; i < N; i++) { p[i] = Integer.parseInt(br.readLine()); } m = new int[D]; for (int i = 0; i < D; i++) { m[i] = Integer.parseInt(br.readLine()); } for (int v : m) { System.out.println(search(v, p)); } } catch (Exception e) { e.printStackTrace(); } } }