Concours AtCoder 462 : Explorer les approches de résolution
Le Beginner Contest 462 d’AtCoder s’est achevé avec cinq problèmes mettant à l’épreuve des compétences allant du traitement de chaînes à la combinatoire. Un participant a récemment partagé son analyse post-concours, détaillant sa démarche et ses solutions Python pour chaque problème de A à E, offrant ainsi des exemples concrets pour apprendre.
Des chaînes aux ensembles : extraire des chiffres et cartographier des cadeaux
Le problème A consistait à extraire tous les chiffres d’une chaîne mixte et à les afficher dans l’ordre. L’auteur a d’abord vérifié chaque caractère en le comparant à la liste des chiffres « 0 » à « 9 » avant de découvrir la méthode isdigit() de Python, qui a simplifié la vérification. Le problème B s’est tourné vers des réseaux sociaux : étant donné qui a envoyé des cadeaux à qui parmi N personnes, la tâche était de lister chaque expéditeur pour chaque destinataire. La solution a construit un dictionnaire associant chaque personne à une liste d’expéditeurs, en itérant deux fois – une pour initialiser et une autre pour remplir – avant d’afficher les comptes et les listes.
Géométrie, criminalité et comptage efficace
Le problème C a abordé la géométrie plane, demandant combien de points se situent en dehors de tout rectangle aligné sur les axes formé par le plus petit x et le plus petit y parmi les points précédents. L’auteur a trié les points par coordonnée x et les a parcourus tout en suivant le minimum de y rencontré jusqu’alors ; chaque fois qu’un nouveau minimum de y apparaissait, le point correspondant ne pouvait être couvert par aucun rectangle précédent, incrémentant ainsi le compte. Le problème D a introduit un scénario de criminalité : trouver des paires valides de suspects ayant été présents dans un établissement pendant toute la durée d’un crime d’une durée D. La solution a utilisé un tableau de type sweep-line pour marquer les moments d’entrée et de sortie des suspects dans la fenêtre « valide » (T_i − D + 1 à S_i), calculé les sommes préfixes pour compter combien étaient présents à chaque instant, puis appliqué une formule simple de combinaisons pour sommer les paires à travers tous les instants.
Enseignements pour les programmeurs compétitifs
Le participant a souligné l’importance de la clarté plutôt que de l’astuce, notant comment des utilitaires Python comme isdigit() ou le tri intégré simplifiaient des boucles autrement manuelles. Pour des contraintes plus élevées, les sommes préfixes et les mises à jour incrémentielles ont maintenu l’efficacité des solutions. L’article sert à la fois de rappel pour les anciens participants et de référence concise pour quiconque aborde des défis similaires.
Source : DEV Community. Synthèse éditoriale assistée par IA — TechnoExpress.