http://paiza.jp/poh/ec-campaign/result/3c7e1ae7a3b70790db8da0ef6c287c11
Hintergrundinformationen und Details zu Problemen https://paiza.jp/poh/ec-campaign Bitte beziehen Sie sich auf. # paizahack_01
Wenn Sie versuchen, die optimale Lösung mit einer Kombination aller Produkte zu finden, ist dies normalerweise $ O (DN ^ 2) $ (dies ist die von paiza erstellte Modellantwort, sodass nur case1 erfolgreich ist). Um dies zu vermeiden und es zu $ O (DN \ log N) $ zu machen, habe ich eine Dichotomie wie diese verwendet:
scanf () einqsort ()Dieser Code hat jedoch das peinliche Ergebnis, dass case3 eine Zeitüberschreitung aufweist. In Eile erstellte ich einen Benchmark-Input, der Fall 3 entspricht, und begann mit der Optimierung, damit ich die vorliegende Leistung quantifizieren konnte.
Das leichte Profilieren dauert zu lange, um es zu erkunden. Da es so groß wie $ D = 300 $ ist, gibt es keine Hilfe dafür, es sei denn, es sind weniger als 0,01 Sekunden pro Suche. Daher wurde der Suchalgorithmus drastisch geändert.
Da wir die Summe der Preise der beiden Produkte optimieren möchten, müssen wir für die Suche nur ein Paar von jeder Seite erstellen. Wenn die Summe den Kampagnenpreis überschreitet, versuchen Sie, das höhere Produkt in das billigere Produkt umzuwandeln. Wenn es unter dem Kampagnenpreis liegt und Sie die vorläufige Lösung bis zu diesem Zeitpunkt verbessern möchten, aktualisieren Sie sie und versuchen Sie, das billigere Produkt durch ein höheres Produkt zu ersetzen. Wenn es dem Kampagnenpreis entspricht, ist es die endgültige Lösung, und wenn es keine Lösung gibt, die zum Ende passt, ist die vorläufige Lösung zu diesem Zeitpunkt die endgültige Lösung.
Als Anfangswert für die Suche sollte der billigere mit dem Artikel mit dem niedrigsten Preis beginnen, während der höhere mit dem Kampagnenpreis abzüglich des Artikels mit dem niedrigsten Preis beginnen sollte. Diese Position kann durch die Dichotomie gefunden werden, die auch im ursprünglichen Algorithmus vorhanden war, und eine gewisse Verbesserung ist möglich.
Mit dieser Richtlinie ist $ O (DN) $ für den Suchteil ausreichend. Tatsächlich wurde die Suchzeit für den Benchmark drastisch reduziert, und alle 300 können in 0,01 Sekunden oder weniger ausgeführt werden. Insgesamt dauert es jedoch etwas weniger als 0,30 Sekunden.
Das nächste, was ich tat, war sortieren. qsort () ist ein Overhead, da es die Vergleichsfunktion intern viele Male aufruft. Um dies zu lösen, habe ich meine eigene nicht rekursive Zusammenführungssortierung erstellt. Es dauert jedoch etwas mehr als 0,20 Sekunden.
Plötzlich wurde mir klar, dass es höchstens 1000000 Arten von Produktpreisen gab, und ich entschied mich für eine $ O (N) $ -Eimersorte. Als dies implementiert wurde, dauerte es etwas mehr als 0,10 Sekunden.
Ich denke jedoch, dass es an erster Stelle notwendig ist, zu sortieren, selbst wenn ich mit dem Eingabewert in jedem Bucket der Bucket-Sortierung suche, denke ich, dass dies die Suchzeit nicht so sehr beeinflussen sollte, da die Anzahl der Produkte und die Anzahl der Buckets unterschiedlich sind, also habe ich es implementiert Hat. Als Nebeneffekt ist es nicht mehr erforderlich, nach dem höheren Startpreis in der Hälfte zu suchen. Diese Verbesserung ändert die Reihenfolge nicht, aber jetzt sind es weniger als 0,10 Sekunden.
Bei den bisherigen Verbesserungen ist die Sortierzeit Null (einfach in den Bucket legen) und die Suche selbst erfolgt innerhalb von 0,01 Sekunden, was die Eingabeverarbeitung bleibt.
Zuerst habe ich "scanf ()" gestoppt und durch "fgets ()" und "strtol ()" ersetzt. Dies ist ungefähr 0,04 Sekunden. Das "scanf ()" war nur für das "% d" schwer.
Um den Aufwand für den Aufruf der Funktion vollständig zu beseitigen, bereiten Sie statt der Verarbeitung jeder Zeile einen großen Puffer vor, der die gesamte Datei enthält, und lesen Sie das Ganze mit "fread ()" und einem numerischen Wert in Ihrer eigenen Eingabefunktion Als ich es so änderte, dass es alles dekodierte, konnte ich endlich auf 0,01 Sekunden und 0,02 Sekunden beschleunigen.
Es kann möglich sein, es ein wenig weiter zu verbessern, indem das Vorhandensein oder Fehlen eines Leerraums in der Eingabe und im Zeilenvorschubcode entschieden wird.
Ich ignoriere die Details (obwohl nicht so detailliert) wie die Verwendung globaler Variablen, das Core-Dumping bei unerwarteten Eingaben, das Fehlen von Testcode usw.
Immerhin ist Ordnung wichtig. Es ist Zeit für eine Feinabstimmung, nachdem die Reihenfolge nicht mehr verbessert werden kann.
Der endgültige Code wird unten angezeigt, ist aber viel länger.
#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;
}
Recommended Posts