こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。
C: paiza事務局作成コード Vol.3 O(DN)
通過テストケース数：3
実行時間(テストケース１)：0.01秒
実行時間(テストケース２)：0.01秒
実行時間(テストケース３)：0.67秒
#include <stdio.h>
#include <stdlib.h>
int CompareInt(const void *_v1, const void *_v2) {
int v1 = *((const int *)_v1);
int v2 = *((const int *)_v2);
if (v1 == v2) return 0;
return v1 > v2 ? 1 : -1;
}
int main(void) {
int N, D; scanf("%d %d", &N, &D);
int p[500000];
int i;
for(i = 0; i < N; i++) {
scanf("%d", &p[i]);
}
qsort(p, N, sizeof(int), CompareInt);
for(i = 0; i < D; i++) {
int m; scanf("%d", &m);
int h = 0, t = N - 1;
int ans = 0;
while(h != t) {
int s = p[h] + p[t];
if (s > m) t--;
else {
if (ans < s) ans = s;
h++;
}
}
printf("%d\n", ans);
}
return 0;
}
C: paiza事務局作成コード Vol.2 O(DNlogN)
通過テストケース数：２
実行時間(テストケース１)：0.01秒
実行時間(テストケース２)：0.04秒
実行時間(テストケース３)：--
#include <stdio.h>
#include <stdlib.h>
int CompareInt(const void *_v1, const void *_v2) {
int v1 = *((const int *)_v1);
int v2 = *((const int *)_v2);
if (v1 == v2) return 0;
return v1 > v2 ? 1 : -1;
}
int UpperBound(int *p, int N, int r) {
int lb = 0, ub = N; //[lb, ub)
while(ub - lb != 1) {
int mid = (ub + lb) / 2;
if (p[mid] <= r) lb = mid;
else ub = mid;
}
return ub;
}
int main(void) {
int N, D; scanf("%d %d", &N, &D);
int p[500000];
int i,j;
for(i = 0; i < N; i++) {
scanf("%d", &p[i]);
}
qsort(p, N, sizeof(int), CompareInt);
for(i = 0; i < D; i++) {
int m; scanf("%d", &m);
int ans = 0;
for(j = 0; j < N; j++) {
int r = m - p[j];
int ub = UpperBound(p, N, r);
ub--;
if (j >= ub) continue;
if (p[ub] > r) continue;
int s = p[j] + p[ub];
if (s <= m && ans < s) {
ans = s;
}
}
printf("%d\n", ans);
}
return 0;
}
C: paiza事務局作成コード Vol.1 O(DN^2)
通過テストケース数：１
実行時間(テストケース１)：0.08秒
実行時間(テストケース２)：--
実行時間(テストケース３)：--
#include <stdio.h>
int main(void) {
int N, D; scanf("%d %d", &N, &D);
int p[500000];
int i, j, k;
for(i = 0; i < N; i++) {
scanf("%d", &p[i]);
}
for(i = 0; i < D; i++) {
int m; scanf("%d", &m);
int ans = 0;
for(j = 0; j < N; j++) {
for(k = j + 1; k < N; k++) {
int s = p[j] + p[k];
if (s > m) continue;
if (ans < s) ans = s;
}
}
printf("%d\n", ans);
}
return 0;
}
