こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
Java: paiza事務局作成コード Vol.4 O(DN)
通過テストケース数：3
実行時間(テストケース１)：0.08秒
実行時間(テストケース２)：0.10秒
実行時間(テストケース３)：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
実行時間(テストケース１)：0.09秒
実行時間(テストケース２)：0.26秒
実行時間(テストケース３)：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
実行時間(テストケース１)：0.10秒
実行時間(テストケース２)：3.41秒
実行時間(テストケース３)：--
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)
通過テストケース数：１
実行時間(テストケース１)：0.15秒
実行時間(テストケース２)：--
実行時間(テストケース３)：--
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();
}
}
}
