Grades

http://paiza.jp/poh/ec-campaign/result/3c7e1ae7a3b70790db8da0ef6c287c11

Pour le contexte et les détails des problèmes https://paiza.jp/poh/ec-campaign Prière de se référer à. # paizahack_01

Algorithme original

Normalement, si vous essayez de trouver la solution optimale avec une combinaison de tous les produits, ce sera $ O (DN ^ 2) $ (c'est la réponse modèle créée par paiza, donc seul le cas1 passera). Pour éviter cela et en faire $ O (DN \ log N) $, j'ai utilisé une dichotomie comme celle-ci:

Entrez avec scanf () comme d'habitude
Triez la liste de prix des produits avec qsort () comme d'habitude
Procédez comme suit pour chaque prix de campagne
Divisez la recherche de produits avec des prix associés pour chaque produit
Afficher la valeur optimale parmi eux

Cependant, ce code a le résultat embarrassant que case3 expire. En toute hâte, j'ai créé une entrée de référence équivalente au cas 3 et j'ai commencé le réglage afin de pouvoir quantifier les performances à portée de main.

Chemin vers la forme finale

Exploration améliorée

Le profilage léger prend trop de temps à explorer. Puisqu'il est aussi grand que $ D = 300 $, il n'y a aucune aide pour cela sauf s'il est inférieur à 0,01 seconde par recherche. Par conséquent, l'algorithme de recherche a été radicalement modifié.

Puisque nous voulons optimiser la somme des prix des deux produits, il suffit de faire une paire de chaque côté pour rechercher. Si le total dépasse le prix de la campagne, essayez de remplacer le produit le plus élevé par le produit le moins cher. S'il est inférieur au prix de la campagne, si vous souhaitez améliorer la solution provisoire jusqu'à ce point, mettez-la à jour et essayez de remplacer le produit moins cher par un produit supérieur. S'il correspond au prix de la campagne, c'est la solution finale, et s'il n'y a pas de solution qui correspond à la fin, la solution provisoire à ce moment-là est la solution finale.

En tant que valeur initiale de recherche, la valeur la moins chère doit commencer par l'article le moins cher, tandis que la valeur la plus élevée doit commencer par le prix de la campagne moins le prix de l'article le moins cher. Cette position peut être trouvée par la dichotomie qui était également dans l'algorithme d'origine, et une certaine amélioration est possible.

Avec cette politique, $ O (DN) $ est suffisant pour la partie de recherche. En fait, le temps de recherche a été considérablement réduit pour le benchmark, et les 300 peuvent être exécutés en 0,01 seconde ou moins. Cependant, cela prend un peu moins de 0,30 seconde dans son ensemble.

Tri amélioré

La prochaine chose que j'ai faite a été de trier. qsort () est une surcharge car il appelle la fonction de comparaison plusieurs fois en interne. Pour résoudre ce problème, j'ai créé mon propre tri de fusion non récursif. Cependant, cela prend un peu plus de 0,20 seconde.

Soudain, je me suis rendu compte qu'il y avait au plus 1000000 types de prix de produits, j'ai donc décidé d'utiliser un tri seau $ O (N) $. Lorsque cela a été mis en œuvre, cela a pris un peu plus de 0,10 seconde.

Cependant, je pense qu'il est nécessaire de trier en premier lieu, même si je recherche avec la valeur d'entrée dans chaque seau du tri seau, je pense que le nombre de produits et le nombre de seaux sont différents, donc cela ne devrait pas tant affecter le temps de recherche, alors je l'ai implémenté Fait. En tant qu'effet secondaire, il n'est plus nécessaire de rechercher le prix de départ le plus élevé de moitié. Cette amélioration ne change pas l'ordre, mais c'est maintenant moins de 0,10 seconde.

Entrée améliorée

Avec les améliorations apportées jusqu'à présent, le temps de tri est nul (il suffit de le mettre dans le seau) et la recherche elle-même est à moins de 0,01 seconde, ce qui reste le traitement d'entrée.

Tout d'abord, j'ai arrêté scanf () et l'ai remplacé par fgets () et strtol (). C'est environ 0,04 seconde. Le scanf () était lourd juste pour le "% d ".

Ensuite, afin d'éliminer complètement la surcharge de l'appel de fonction, au lieu de traiter chaque ligne, préparez un grand tampon contenant le fichier entier et lisez le tout avec fread (), et la valeur numérique dans votre propre fonction d'entrée Quand je l'ai changé pour qu'il décode tout, j'ai finalement pu accélérer jusqu'à 0,01 seconde et 0,02 seconde.

Il peut être possible de l'améliorer un peu plus en décidant de la présence ou de l'absence d'espace blanc dans l'entrée et le code de saut de ligne.

Résumé

J'ignore ces détails (bien que ce ne soit pas détaillé) tels que l'utilisation de variables globales, le dumping de base lorsqu'une entrée inattendue est donnée, le manque de code de test, etc.

Après tout, l'ordre est important. Il est temps de peaufiner la commande après que la commande ne puisse plus être améliorée.

code

Le code final est montré ci-dessous, mais il est beaucoup plus long.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

#define MIN_PRICE (10)
#define MAX_PRICE (1000000)
#define MIN_LIMIT (10)
#define MAX_LIMIT (1000000)
#define MAX_PRODUCTS (500000)
#define MAX_DAYS (300)
#define MAX_INPUT_BYTES (6+1+3+1+(7+1)*MAX_PRICE+(7+1)*MAX_DAYS)

int pricebucket[MAX_PRICE+1];
int m_j[MAX_DAYS];
int N;
int D;

// read prices from buffer. it is faster than calling strtol many times.
void
readprices(char **p) {
  char c;
  int price;
  int i;

  for (i = 0; i < N; i++) {
    price = 0;
    for (;;) {
      c = *(*p)++;
      if (isdigit(c)) {
        price = price*10 + c - '0';
      } else {
        if (price >= MIN_PRICE) {
          pricebucket[price]++;
          break;
        }
      }
    }
  }
}

// read limits from buffer. it is faster than calling strtol many times.
void
readlimits(char **p) {
  char c;
  int limit;
  int j;

  for (j = 0; j < D; j++) {
    limit = 0;
    for (;;) {
      c = *(*p)++;
      if (isdigit(c)) {
        limit = limit*10 + c - '0';
      } else {
        if (limit >= MIN_LIMIT) {
          m_j[j] = limit;
          break;
        }
      }
    }
  }
}

// search prices for the pair of products so that
// their total price is nearest to and less than or equal to the limit.
// return the total price.
int
searchpair(int limit) {
  int l = MIN_PRICE;
  int r = (limit - l <= MAX_PRICE) ? limit - l : MAX_PRICE;
  int currentmax = 0;
  int total;

  // check if there is a pair of product with prices l and r.
  while (l <= r) {
    total = l+r;
    if (total <= limit && pricebucket[r] > 0) {
      if (pricebucket[l] > 0) {
        if (total > currentmax && (l < r || pricebucket[l] > 1)) {
          // better pair of different products
          currentmax = total;
          if (currentmax == limit) {
            break;
          }
        }
      }
      l++;
    } else {
      r--;
    }
  }
  return currentmax;
}

int
main(void) {
  int i, j, p;
  char *buf;
  int bufsize;
  char *dp;

  // use 1 fread + strtol's for read numbers.
  // they are faster than scanf.
  buf = malloc(MAX_INPUT_BYTES+1);
  if (!buf) exit(1);
  bufsize = fread(buf, 1, MAX_INPUT_BYTES, stdin);
  buf[bufsize] = '\0'; // any non-digit character

  N = strtol(buf, &dp, 10);
  D = strtol(dp, &dp, 10);

  // read prices.
  // prices are not stored in an array.  just use buckets of prices.
  readprices(&dp);

  // read limits.
  readlimits(&dp);

  // compute the answer.
  for (j = 0; j < D; j++) {
    printf("%d\n", searchpair(m_j[j]));
  }

  return 0;
}

Recevoir des compliments de nouvelles filles en C # paizahack_01