Pour moi, à la lecture de l'énoncé, je n'y ai pas vu un problème d'algorithmique, mais de mathématiques. Une régate avec un temps de charge qui donne la vitesse pour dépasser la distance record en un temps limité, c'est une inéquation polynomiale de second degré.
Un polynôme de second degré
Soit T la durée de la course, D la distance record et t le temps de charge (notre variable). La vitesse atteinte est d'après l'énoncé égale au temps de charge. Sur la durée de la course, il ne reste plus que T - t pendant lequel le bateau parcourra v (T - t) = t(T - t).
On charge à battre le record, soit :
Cela se normalise en :
La partie gauche est un polynôme de second degré, en forme de cloche vers le haut. Ça tombe bien, si les données sont bien construites il devrait s'annuler en deux points, et être négatif entre les deux. Je sais très bien résoudre ça.
Résolution
Le discriminant de ce polynôme vaut :
Comme je disais, si les données sont bien construites, ça devrait être strictement positif et donner les racines suivantes :
En chargeant notre bateau pendant exactement t_1 ou t_2, on égale le record. Entre t_1 et t_2, on le dépasse.
Retour à la (削除) réalité (削除ここまで) fiction
Bon, c'est bien joli ça, on peut déterminer des temps minimum et maximum qui sont des réels, mais on nous demande un nombre de durées de charge possible, entières à la milliseconde près, pour dépasser strictement le record.
Si le temps minimum, par exemple, n'est pas entier, c'est facile, il faut charger pendant une durée supérieur ou égale à son arrondi à l'entier supérieur. Mais les cas limites sont importants, qu'en est-il si le temps minimum est entier ? Il faut charger pendant une durée supérieure ou égale à l'entier suivant.
En fait, la borne inférieure à considérer est l'entier inférieur au temps minimum, augmenté d'une unité. Mutatis mutandis pour le temps maximum.
Les bornes incluses de notre intervalle de durées possibles seront donc :
Quand au nombre d'options, c'est par conséquent la longueur de cet intervalle :
Partie 1, partie 2
Ce calcul s'applique aussi bien à la première qu'à la deuxième partie. Et c'est rapide, genre vraiment rapide puisque c'est simplement du calcul. Mieux encore, alors que pour la première partie il faut traiter trois ou quatre régates, pour la seconde il n'y en a plus qu'une seule, donc c'est trois ou quatre fois plus rapide. :-)
En pratique, en Python 3 ça prend dans les 50 millisecondes pour la première comme pour la seconde partie, mais je soupçonne que ce soit essentiellement la compilation et le temps de chargement de la machine virtuelle Python.
# Maths
Posté par 🚲 Tanguy Ortolo (site web personnel) . En réponse au message Advent of Code 2023, day 6. Évalué à 6. Dernière modification le 06 décembre 2023 à 11:06.
Pour moi, à la lecture de l'énoncé, je n'y ai pas vu un problème d'algorithmique, mais de mathématiques. Une régate avec un temps de charge qui donne la vitesse pour dépasser la distance record en un temps limité, c'est une inéquation polynomiale de second degré.
Un polynôme de second degré
Soit T la durée de la course, D la distance record et t le temps de charge (notre variable). La vitesse atteinte est d'après l'énoncé égale au temps de charge. Sur la durée de la course, il ne reste plus que T - t pendant lequel le bateau parcourra v (T - t) = t(T - t).
On charge à battre le record, soit :
Cela se normalise en :
La partie gauche est un polynôme de second degré, en forme de cloche vers le haut. Ça tombe bien, si les données sont bien construites il devrait s'annuler en deux points, et être négatif entre les deux. Je sais très bien résoudre ça.
Résolution
Le discriminant de ce polynôme vaut :
Comme je disais, si les données sont bien construites, ça devrait être strictement positif et donner les racines suivantes :
En chargeant notre bateau pendant exactement t_1 ou t_2, on égale le record. Entre t_1 et t_2, on le dépasse.
Retour à la
(削除) réalité (削除ここまで)fictionBon, c'est bien joli ça, on peut déterminer des temps minimum et maximum qui sont des réels, mais on nous demande un nombre de durées de charge possible, entières à la milliseconde près, pour dépasser strictement le record.
Si le temps minimum, par exemple, n'est pas entier, c'est facile, il faut charger pendant une durée supérieur ou égale à son arrondi à l'entier supérieur. Mais les cas limites sont importants, qu'en est-il si le temps minimum est entier ? Il faut charger pendant une durée supérieure ou égale à l'entier suivant.
En fait, la borne inférieure à considérer est l'entier inférieur au temps minimum, augmenté d'une unité. Mutatis mutandis pour le temps maximum.
Les bornes incluses de notre intervalle de durées possibles seront donc :
Quand au nombre d'options, c'est par conséquent la longueur de cet intervalle :
Partie 1, partie 2
Ce calcul s'applique aussi bien à la première qu'à la deuxième partie. Et c'est rapide, genre vraiment rapide puisque c'est simplement du calcul. Mieux encore, alors que pour la première partie il faut traiter trois ou quatre régates, pour la seconde il n'y en a plus qu'une seule, donc c'est trois ou quatre fois plus rapide. :-)
En pratique, en Python 3 ça prend dans les 50 millisecondes pour la première comme pour la seconde partie, mais je soupçonne que ce soit essentiellement la compilation et le temps de chargement de la machine virtuelle Python.