Programmation compétitive — par où commencer

Que vous débutiez votre premier cours d'algorithmique ou que vous soyez un vétéran du métier, il est toujours bon d'accueillir de nouvelles personnes dans ce loisir ! Cet article vous présentera les ressources clés dont vous aurez besoin pour plonger dans la programmation compétitive.

Notez que je la traite comme un loisir, mais vous êtes libre de tenter de devenir le prochain Gennady Korotkevich (le Magnus Carlsen de notre discipline) — je trouve sain d'avoir un objectif, mais c'est encore mieux de se laisser porter et de finir bien au-delà de ce que l'on croyait être ses limites.

La programmation compétitive, aussi appelée sport programming, est un formidable sport cérébral, très populaire chez les lycéens et étudiants pour ses énigmes très exigeantes tournant autour de problèmes mathématiques et algorithmiques.

C'est un récapitulatif que je n'avais jamais pris le temps d'écrire lorsque j'étais enseignant ; je me suis donc dit que c'était mieux maintenant que jamais.

Avant de poursuivre, je voudrais remercier tous mes étudiants, passés ou actuels, qui ont abordé la programmation compétitive avec passion et qui ont suivi mon intérêt démesuré pour le sujet. Avec une mention spéciale à Alexandre Douard, sans qui rien de tout cela ne serait possible.

Pourquoi la programmation compétitive ?

Je suppose que la plupart d'entre vous connaissez déjà la programmation compétitive et voulez simplement trouver des ressources utiles : alors faites défiler ! Pour celles et ceux qui tombent sur cet article, laissez-moi vous chanter une ode à la programmation compétitive :

La compétition pimente les choses, mais au fond, le plaisir réside dans ce que l'on apprend en chemin. Les algorithmes.

Les algorithmes sont le carburant pour comprendre le fonctionnement de nos systèmes ; ils sont la clé pour devenir un informaticien efficace.

Maîtriser les algorithmes est l'une des compétences les plus importantes que l'on puisse avoir, et le faire à travers le prisme de la programmation compétitive est incroyablement gratifiant.

Au-delà de la fierté personnelle, cela peut vous aider à décrocher un emploi ! Les leaders de l'industrie le savent : de l'IOI à l'ICPC, les compétitions sont sponsorisées et suivies de près par les géants. Ils veulent les esprits les plus brillants pour résoudre leurs problèmes, et cela passe par les algorithmes.

Même si vous ne concourez pas, cela vous sera utile lors des entretiens techniques.

Démarrage pour débutants

Vous ne connaissez que très peu les algorithmes ou la programmation compétitive ? Commencez ici ! Suivez les liens au fil de l'eau, ayez confiance en vous et amusez-vous !

Quel langage utiliser ?

Ne réfléchissez pas trop : choisissez votre langage préféré, ou un que vous aimeriez essayer. Peu importe, tant qu'il est assez populaire. La liste des langages supportés par l'ICPC est : Python, Java, C++, C, Kotlin ; mais si vous aimez vraiment Rust ou OCaml, utilisez-les.

Un langage que vous aimez utiliser vous mènera bien plus loin qu'un que vous détestez.

Qu'est-ce qu'un problème de programmation compétitive ?

Il se découpe en trois grandes parties :

• L'énoncé et le contexte — la partie où l'on vous explique le concept central du problème (par ex. Bob veut trouver son chemin dans un labyrinthe).
• Les cas de test d'exemple et les contraintes — la partie où l'on vous donne les sorties attendues pour des entrées données, ainsi que les contraintes de temps et de mémoire.
• Les cas de test cachés — la partie « fun », celle qui teste votre programme sur de nouveaux cas inédits.

On attend généralement de vous que vous résolviez tous les cas de test pour valider le problème.

Les outils dont vous avez besoin

Un éditeur de texte et le compilateur / interpréteur de votre langage préféré sont un excellent point de départ.

Je vous conseille aussi une feuille de papier et un stylo, ça peut être bien pratique.

Livres

Cette petite sélection est une bonne base à avoir dans sa bibliothèque quel que soit votre niveau, mais elle est particulièrement utile si vous débutez et que vous aimez avoir un support physique sous la main.

• Competitive Programming in Python, par Christoph Dürr & Jill-Jênn Vie — Un superbe livre tout-en-un, accompagné de leur excellente plateforme TryAlgo et de leur bibliothèque très utile.
• Guide to Competitive Programming: Learning and Improving Algorithms Through Contests, par Antti Laaksonen — Un panorama des concepts clés et du « milieu », principalement en C++.
• Introduction to Algorithms, par Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest et Clifford Stein — Très bonne vulgarisation et introduction approfondie si vous êtes à l'aise avec les maths.

Sites pour apprendre

Hello Algo : un site brillant qui a tout ce qu'il faut, explorez-le !

Le GitHub de Kaish : un bon récapitulatif ; cela recoupe parfois ce que je dis ici, mais c'est assez complet.

VisuAlgo : si vous ne connaissez pas encore VisuAlgo, allez y jeter un œil, c'est génial pour visualiser les algorithmes.

Cp-algorithms : proche de Hello Algo, interface moins soignée mais contenu tout aussi bon.

Sites d'entraînement

C'est là que le vrai plaisir commence ! Ouvrez-les et essayez-les, vous serez accro en un rien de temps.

CodinGame : très connu en France, notamment chez les très jeunes étudiants et dans de nombreux processus de recrutement. C'est une très bonne introduction à certains concepts, et il apporte la compétitivité de façon très ludique. Encore plus fun entre amis. C'est là que tout le monde devrait commencer pour savoir si c'est fait pour soi.

LeetCode : le site de programmation compétitive le plus célèbre, créé par une entreprise américaine pour préparer les entretiens techniques. Il a tout, et il est assez souple sur l'acceptation : il n'est pas toujours nécessaire d'implémenter la meilleure version d'un algorithme pour passer les tests. Quand vous commencez à réussir les problèmes difficiles, il est peut-être temps de passer à la section Intermédiaire de cet article !

Quand serai-je assez bon ?

Assez bon pour quoi ? Être finaliste de l'ICPC ? Battre quelques problèmes moyens sur LeetCode pour réussir des entretiens ?

Ne traitez pas la programmation compétitive comme une échelle à gravir : amusez-vous, et vous serez meilleur que 99 % des autres programmeurs pour résoudre des problèmes algorithmiques en un rien de temps !

Niveau intermédiaire et au-delà

Vous avez suivi des cours de programmation compétitive, codé des heures sur LeetCode, et même tenté une première compétition, mais vous ne savez pas où aller ensuite ? Suivez le guide !

Livres

Competitive Programming 4, par Steven Halim et Felix Halim — Le tout-en-un dont vous aurez jamais besoin, la bible de l'étudiant en programmation compétitive.

Competitive Programmer's Handbook, par Antti Laaksonen — Je le trouve très pratique ; c'est une excellente plongée dans les algorithmes avancés et les concepts propres à la programmation compétitive.

Outils

Il est temps d'aller plus loin : configurez votre environnement pour gagner en vitesse :

• Competitive Programming Helper (CPH) — La seule extension dont vous aurez jamais besoin, fonctionne parfaitement sous Visual Studio Code.
• Competitive Companion — Une extension Chrome qui permet d'exporter les cas de test du problème en cours.
• Si vous n'aimez pas CPH, Code Runner fera l'affaire.
• Un notebook — un document qui compile de nombreuses implémentations d'algorithmes et de bonnes pratiques ; vous pouvez écrire le vôtre ou utiliser un existant, comme le très célèbre notebook de Stanford.

Sites d'entraînement

• Kattis : le site islandais qui répond à tous vos besoins — une interface agréable (dans le genre de LeetCode) mais avec des problèmes bien plus difficiles et un classement (imparfait, mais existant). Vous pouvez même récupérer vos identifiants Kattis puis, grâce à Kattis-cli, tout faire depuis votre terminal. Il est facile de créer des compétitions et de s'affronter entre étudiants ou universités. Surtout populaire en Occident.
• Codeforces : le géant, celui qui les domine tous. Il est à la programmation compétitive ce que chess.com est aux échecs. Des problèmes plus difficiles, de nombreuses compétitions hebdomadaires, un ELO, une communauté grande et active. C'est l'endroit où être si vous prenez ce loisir au sérieux. Surtout populaire à l'est, mais gagne régulièrement le reste du monde.
• AtCoder : moins connu, mais une très bonne ressource.
• Anciens jeux de problèmes de l'ICPC : on les trouve sur divers sites, dont celui en lien ici qui regroupe la plupart des jeux de problèmes des qualifications régionales.

Où briller maintenant que je suis assez bon pour la compétition ?

Cela dépend vraiment de l'endroit où vous vous trouvez et de votre âge : les options à votre disposition peuvent grandement changer. Demandez à vos professeurs ou contactez l'université locale.

Mais pour la plupart, le Graal serait les finales mondiales de l'ICPC. Trouvez vos qualifications régionales locales sur leur site. Renseignez-vous aussi sur l'IOI, la Yandex Cup et la Meta Hacker Cup, qui sont les autres grandes compétitions.

Les qualifications de l'ICPC sont une expérience formidable, le plaisir est garanti, même si vous ne gagnez pas, promis.

C'est tout pour aujourd'hui

Il y aurait bien plus à dire, bien plus à découvrir, lire, essayer, mais j'ai dit ce que je considère comme le minimum vital pour que quiconque puisse plonger dans ce monde merveilleux.

Amusez-vous, entraînez-vous, échouez, prenez confiance et réussissez ! Partagez vos exploits en commentaire !

Bonne programmation !