POH! Vol.1 C模範解答

こちらではpaiza事務局側で作成した模範解答を掲載していす。
提出された最速コードは下記リンク先でご覧いただけます。

【POH Vol.1結果発表】新人女子を最も助けたコードとは?

C: paiza事務局作成コード Vol.3 O(DN)

通過テストケース数:3
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.01秒
実行時間(テストケース3):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)

通過テストケース数:2
実行時間(テストケース1):0.01秒
実行時間(テストケース2):0.04秒
実行時間(テストケース3):--

#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)

通過テストケース数:1
実行時間(テストケース1):0.08秒
実行時間(テストケース2):--
実行時間(テストケース3):--

#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;
}
ページの先頭へ戻る