Handbook Python

Competitive Programming
Cheat sheet / manuel de survie hors ligne

Consultation rapide - snippets fiables - reflexes de concours

Concu pour :
— retrouver une syntaxe en quelques secondes,
— copier un snippet sans perdre de temps,
— eviter les oublis sous stress,
— choisir vite la bonne structure de donnees.
Organisation : les notions sont classees par rentabilite pratique en concours, pas par
logique academique.

Contenu
Essentiel absolu template contest, lecture rapide, listes, dictionnaires, tris,
boucles, built-ins
Tres frequent prefix sums, BFS/DFS, Counter, bisect, heapq, binary
search, grilles
Utile regulierement DP, backtracking, compression de coordonnees,
precompute, modular arithmetic
Bonus memoisation, bibliotheque perso, resume express de
derniere minute

Version optimisee pour PDF navigable avec sommaire cliquable, liens internes et signets.
Competitive Programming en Python Handbook hors ligne

Table des matières

Top 20 des syntaxes / fonctions a connaitre absolument 4

1 Introduction ultra courte 4

2 Template Python de base pour contest 5

2.1 Template minimal universel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Template multi-testcases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Template pour entrees volumineuses . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.4 Rappels express de lecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Syntaxe Python essentielle classee par importance 6

3.1 Essentiel absolu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.1.1 Variables et types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.2 Conditions et boucles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3.1.3 Comparaisons et operateurs utiles . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2 Tres frequent en contest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.1 Listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.2 Chaines de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.3 Dictionnaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2.4 Ensembles (set) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.5 Fonctions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.6 Tri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Utile regulierement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.3.1 Idiomes Python pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

4 Fonctions Python ultra utiles en competitive programming 11

4.1 Built-ins indispensables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.2 Module math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.3 Module collections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.4 Module itertools . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4.5 Module bisect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.6 Module heapq . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

5 Snippets prets a copier 13

5.1 Maths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.1 PGCD et PPCM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.2 Factorielle simple et precompute . . . . . . . . . . . . . . . . . . . . . . . . 13
5.1.3 Puissance rapide / exponentiation modulaire . . . . . . . . . . . . . . . . . 14
5.1.4 Test de primalite simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.1.5 Crible d’Eratosthene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.1.6 Facteurs premiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
5.1.7 Modulo classique et inverse modulaire . . . . . . . . . . . . . . . . . . . . . 15

Version concours 1/26

Competitive Programming en Python Handbook hors ligne

5.2 Tableaux / listes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

5.2.1 Prefix sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2.2 Suffix sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2.3 Difference array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2.4 Max / min avec indice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
5.2.5 Suppression des doublons . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.2.6 Compression de coordonnees . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.3 Tri et recherche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.3.1 Tris courants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.3.2 Modele de binary search sur reponse . . . . . . . . . . . . . . . . . . . . . . 16
5.3.3 Lower bound / upper bound style Python . . . . . . . . . . . . . . . . . . . . 16
5.4 Frequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4.1 Compter les occurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4.2 Element le plus frequent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
5.4.3 Groupement simple par cle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5 Files / piles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5.1 Stack avec list . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5.2 Queue avec deque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.5.3 Pattern BFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.6 Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.6.1 Liste d’adjacence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.6.2 DFS iteratif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
5.6.3 DFS recursif . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.6.4 Composantes connexes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.7 Recursion / backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.7.1 Squelette simple . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.7.2 Generation de subsets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
5.7.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.8 Programmation dynamique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.8.1 Template 1D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.8.2 Template 2D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.8.3 Memoisation avec dictionnaire / lru_cache . . . . . . . . . . . . . . . . . . 19
5.9 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.9.1 Palindrome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
5.9.2 Frequences de caracteres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.9.3 Sous-chaines / toutes fenetres de longueur k . . . . . . . . . . . . . . . . . 20
5.10Grilles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.10.1Parcours 2D et voisins 4 directions . . . . . . . . . . . . . . . . . . . . . . . 20
5.10.2Voisins 8 directions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
5.10.3BFS sur grille . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

6 Complexites a connaitre 20
6.1 Ordres de grandeur pratiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Version concours 2/26

Competitive Programming en Python Handbook hors ligne

6.2 Table rapide selon la taille de n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

7 Astuces Python speciales contest 22

8 Pieges frequents 22

9 Mini bibliotheque personnelle de contest 23

10Annexe ultra rapide 25

Version concours 3/26

Competitive Programming en Python Handbook hors ligne

Top 20 des syntaxes / fonctions a connaitre absolument

# Element Syntaxe / exemple Pourquoi c’est rentable

a, b = map(int,
1 Lecture d’entiers Base absolue de la plupart des
input().split())
problemes
input =
2 Lecture rapide Evite les TLE sur gros input
[Link]
for _ in
3 Boucle testcases Pattern de concours ultra frequent
range(t):
arr =
4 Liste d’entiers list(map(int, Lecture standard
input().split()))
5 Tri copie sorted(arr) Tri sans modifier l’original
6 Tri en place [Link]() Plus direct et un peu plus leger
7 Frequences Counter(arr) Compter vite et proprement
8 Dico robuste [Link](x, 0) Evite les KeyError
Appartenance x in seen avec
9 Recherche moyenne en O(1)
rapide set
pref[i+1] =
10 Prefix sums Requetes de sommes rapides
pref[i] + arr[i]
while lo < hi:
11 Binary search Pour optimisation ou recherche de
...
seuil
bisect_left(a,
12 bisect_left Lower bound style C++
x)
13 File BFS q = deque([src]) Parcours de graphe / grille
14 Min-heap heappush(h, x) Priorites, Dijkstra, k plus petits
15 PGCD [Link](a, b) Maths, fractions, divisibilite
Exponentiation
16 pow(a, b, mod) Modulaire en O(log b)
rapide
for i, x in
17 Enumeration Indice + valeur, tres lisible
enumerate(arr):
for a, b in
18 Zip Parcours parallele propre
zip(A, B):
[f(x) for x in
19 Compr. de liste Construction compacte et rapide
arr]
for dr, dc in
20 Visites grille Pattern central pour BFS/DFS sur
dirs:
matrice

1 Introduction ultra courte

Ce PDF est un support de survie rapide. Il ne remplace pas l’entrainement : il sert a
retrouver une syntaxe, un pattern ou un snippet en quelques secondes.

Version concours 4/26

Competitive Programming en Python Handbook hors ligne

Comment l’utiliser en competition

1. Va d’abord au template de base (section 2) pour copier le squelette de depart.
2. Si tu bloques sur la syntaxe, ouvre section 3.
3. Si tu sais deja l’idee mais pas l’implementation, saute a section 5.
4. Si tu hesites sur la faisabilite, verifie section 6.
5. A 5 minutes du debut ou de la fin, consulte l’annexe express en section 10.

A retenir
Convention de lecture : n = taille, arr = liste, mod = 10**9 + 7 quand un modulo
classique est utilise. Les snippets privilegient la clarte et la fiabilite avant la micro-
optimisation.

Erreurs frequentes
Ne te noie pas dans le PDF. En contest, cherche le pattern minimum suffisant. Trop
generaliser fait perdre du temps.

2 Template Python de base pour contest

2.1 Template minimal universel
import sys
input = [Link]

def solve():
n = int(input())
arr = list(map(int, input().split()))
print(sum(arr))

if __name__ == "__main__":
solve()

A retenir
A utiliser quand il n’y a qu’un seul cas de test et une entree classique. C’est le meilleur
point de depart par defaut.

2.2 Template multi-testcases

import sys
input = [Link]

def solve():
n = int(input())
arr = list(map(int, input().split()))
return max(arr) - min(arr)

if __name__ == "__main__":
t = int(input())
out = []
for _ in range(t):
[Link](str(solve()))
[Link]("\n".join(out))

Version concours 5/26

Competitive Programming en Python Handbook hors ligne

Astuce concours
Accumuler les reponses dans out puis faire un seul join est souvent plus propre et plus
rapide qu’une succession de print.

2.3 Template pour entrees volumineuses

import sys

data = [Link]().split()
it = iter(data)

def ni():
return int(next(it))

def solve():
n = ni()
arr = [ni() for _ in range(n)]
return sum(arr)

ans = solve()
[Link](str(ans))

A retenir
Reserve ce pattern aux tres grosses entrees. Il est excellent pour les problemes pu-
rement numeriques, moins pratique si le parsing est complexe ou melange nombres /
chaines.

2.4 Rappels express de lecture

Besoin Syntaxe Remarque

Un entier n = int(input()) Base

a, b = map(int,
Deux entiers Ultra frequent
input().split())
arr = list(map(int,
Liste d’entiers Standard
input().split()))
Une chaine s = input().strip() strip() enleve \n
grid =
Une grille de caracteres [input().strip() for _ Chaque ligne = chaine
in range(n)]
mat = [list(map(int,
Liste de listes input().split())) for Matrice numerique
_ in range(n)]

3 Syntaxe Python essentielle classee par importance

3.1 Essentiel absolu

Version concours 6/26

Competitive Programming en Python Handbook hors ligne

3.1.1 Variables et types

Element Syntaxe Exemple Quand / pieges

n =
Entier int(x) Type principal en contest
int(input())
x =
Flottant float(x) Rare ; attention precision
float(input())
Chaine str(x) s = str(123) Pour concatener / afficher
Booleen bool(x) ok = (a < b) Tres utile dans les tests
Tuple (a, b) pt = (x, y) Immuable, cle de dico
possible
Liste [1, 2, 3] arr = [] Structure la plus frequente
Set {1, 2, 3} seen = set() Appartenance rapide
Dict {'a': 1} freq = {} Mapping / comptage

Erreurs frequentes
input() renvoie toujours une chaine. Les oublis de conversion vers int sont une source
constante de bugs.

3.1.2 Conditions et boucles

Element Exemple Utilisation / pieges

if x > 0: ... elif x

Condition Branches classiques
== 0: ... else: ...
Boucle for for i in range(n): Quand le nombre d’iterations est connu
Boucle while while lo < hi: Binary search, simulations
Break break Sort de la boucle courante
Continue continue Saute a l’iteration suivante
Pass pass Placeholder, rarement utile en contest
Range range(l, r, step) r exclu
for i, x in
Enumerate Indice + valeur
enumerate(arr):
for a, b in zip(A,
Zip Parcours parallele
B):
for x in
Reversed Parcours inverse sans copie
reversed(arr):

A retenir
Reflexe utile : range(n) pour les indices, enumerate(arr) si tu veux l’indice et la valeur,
for x in arr si tu veux seulement la valeur.

Version concours 7/26

Competitive Programming en Python Handbook hors ligne

3.1.3 Comparaisons et operateurs utiles

Operateur Exemple Remarque

Division entiere a // b Important : pas une vraie division

Modulo a % b Cyclage, parite, arithmetique modulaire
Puissance a ** b Preferer pow(a, b, mod) si modulo
Appartenance x in s Tres rentable avec set et dict
Logique and / or / not Conditions composees
Comparaison
0 <= x < n Lisible et pythonique
chainee
Egalite multiple if x in (1, 3, 5): Souvent plus net qu’une chaine de or

3.2 Tres frequent en contest

3.2.1 Listes

Action Syntaxe / exemple Quand l’utiliser / pieges

Creation arr = [0] * n Initialisation rapide

Acces arr[i] Indices de 0 a n-1
Slicing arr[l:r] r exclu ; copie partielle
Ajout fin [Link](x) O(1) amorti
Ajout multiple [Link](b) Ajoute chaque element de b
Suppression fin [Link]() Renvoie le dernier element
Suppression
[Link](i) O(n) en general
indice
Concat c = a + b Cree une nouvelle liste
sq = [x*x for x in
Compr. de liste Tres pratique
arr]
b = arr[:] ou
Copie Evite l’alias
[Link]()

Erreurs frequentes
b = arr ne copie pas : b et arr pointent vers la meme liste. Pour une matrice,
[[0] * m] * n duplique les references de lignes : a eviter. Utilise [[0] * m for _ in
range(n)].

Version concours 8/26

Competitive Programming en Python Handbook hors ligne

3.2.2 Chaines de caracteres

Action Syntaxe / exemple Quand / pieges

Slice s[l:r] Sous-chaine simple

Split parts = [Link]() Coupe par espaces
Join "".join(chars) Recolle vite une liste de chaines
Strip [Link]() Enleve espaces / \n bords
Recherche [Link]("ab") Renvoie -1 si absent
Presence "ab" in s Test rapide
Remplacement [Link]("a", "b") Cree une nouvelle chaine
Comptage [Link]("a") Simple et utile
Tri caract. "".join(sorted(s)) Canoniser / comparer
Inverse s[::-1] Palindromes, renversement

A retenir
Les chaines sont immutables. Toute ”modification” cree une nouvelle chaine. Si tu fais
beaucoup de changements locaux, passe plutot par list(s).

3.2.3 Dictionnaires

Action Syntaxe / exemple Quand / pieges

Creation d = {} Mapping general

Acces d[key] Suppose que la cle existe
Acces sur [Link](key, 0) Comptage robuste
for k, v in
Parcours items Cle + valeur
[Link]():
Cles / valeurs [Link](), [Link]() Souvent pour iteration
d[x] = [Link](x, 0) +
Increment freq Pattern classique
1
Test presence if x in d: O(1) moyen
Suppression del d[x] Supprime la cle

Astuce concours
Pour les frequences, commence souvent par Counter ou defaultdict(int). Pour un
mapping arbitraire, le dict normal reste le plus universel.

Version concours 9/26

Competitive Programming en Python Handbook hors ligne

3.2.4 Ensembles (set)

Action Syntaxe / exemple Quand / pieges

Creation st = set() Jamais {} seul : c’est un dict vide

Ajout [Link](x) Inserer un element
Suppression
[Link](x) Erreur si absent
stricte
Suppression
[Link](x) Aucun bug si absent
souple
Presence x in st Hyper utile
Union a | b Ensemble des deux
Intersection a & b Elements communs
Difference a - b Dans a mais pas b

3.2.5 Fonctions

Element Exemple Utilite / pieges

def f(x): return x +

Definition Base
1
Retour multiple return a, b Renvoie un tuple
Arguments def f(x, y=0): Parametres par defaut pratiques
Lambda simple key=lambda x: x[1] Surtout pour sorted
Fonction solve def solve(): ... Bonne hygiene concours

3.2.6 Tri

Action Syntaxe / exemple Quand / pieges

Trie copie b = sorted(arr) Garde arr intact

Trie en place [Link]() Economise une copie
sorted(arr,
Descendant Inversion simple
reverse=True)
Cle simple sorted(a, key=len) Trier par taille, etc.
Tuple sorted(pairs) Trie lexicographiquement
Plusieurs sorted(a, key=lambda
Pattern rentable
criteres x: (x[1], -x[0]))

Erreurs frequentes
[Link]() renvoie None. Le bug classique : arr = [Link]().

3.3 Utile regulierement

Version concours 10/26

Competitive Programming en Python Handbook hors ligne

3.3.1 Idiomes Python pratiques

Idiome Exemple Gain

Swap a, b = b, a Echange propre

Unpack x, y = pair Lecture directe
idx, val =
Max avec indice max(enumerate(arr), Evite une boucle manuelle
key=lambda p: p[1])
Dedup ordre tri sorted(set(arr)) Compression / normalisation
Caracteres vers liste chars = list(s) Pour modification
for a, b in zip(arr,
Pair wise simple Adjacences
arr[1:]):

Astuce concours
Python est concis, mais en concours la lisibilite gagne. Un one-liner brillant mais fragile
est souvent une mauvaise affaire.

4 Fonctions Python ultra utiles en competitive programming

4.1 Built-ins indispensables

Fonction Role Complexite Cas d’usage typique

len(x) Taille O(1) Listes, chaines, dicos, sets

sum(arr) Somme O(n) Prefix quick check, total
min(arr) /
Extremes O(n) Bornes, verification
max(arr)
abs(x) Valeur absolue O(1) Distances, ecarts
all(iter) Tous vrais ? O(n) Validation
Au moins un
any(iter) O(n) Detection
vrai ?
map(f, arr) Transformer O(n) Parsing rapide
filter(f,
Filtrer O(n) Rare ; comprehension souvent plus
arr)
lisible
sorted(arr) Tri O(n log n) Base
bin(x) /
Conversions
oct(x) / O(k) Bits, representation
bases
hex(x)
pow(a, b, Expo
O(log b) Incontournable
mod) modulaire
Quotient +
divmod(a, b) O(1) Digits, decomposition
reste

Version concours 11/26

Competitive Programming en Python Handbook hors ligne

4.2 Module math

Fonction Complexite Cas d’usage

[Link](a,
O(log n) Divisibilite, fractions, PGCD
b)
[Link](a,
O(log n) PPCM rapide
b)
[Link](x) O(1) Geometrie, bornes ; attention flottants
[Link](x) O(1) pratique Racine entiere sans flottants
[Link](x),
O(1) Arrondis
[Link](x)
[Link](n)
O(n) Petits n, combinatoire
[Link](n,
variable Combinaisons exactes
k)
[Link](n,
variable Permutations directes
k)

A retenir
En concours, [Link] est souvent plus sure que sqrt pour les tests de primalite ou
√
les boucles jusqu’a n.

4.3 Module collections

Outil Complexite cle Pourquoi c’est fort

Counter O(n) creation Comptage d’occurrences, mode, frequences

O(1) acces
defaultdict(int) Dico qui initialise a 0 automatiquement
moyen
O(1)
deque pop/append Queue BFS, sliding window
aux deux bouts
from collections import Counter, defaultdict, deque

cnt = Counter(arr)
freq = defaultdict(int)
q = deque([start])

4.4 Module itertools

Fonction Idee Cas d’usage

permutations(arr,Tous les
Petits n seulement
r) arrangements
combinations(arr,Choix sans
Subsets de taille fixe
r) ordre
accumulate(arr) Prefix sums Sommes cumulatives propres
product(A, Produit
Enumeration exhaustive
repeat=k) cartesien

Version concours 12/26

Competitive Programming en Python Handbook hors ligne

Erreurs frequentes
[Link] et product explosent tres vite. Tres utile pour n ≤ 8 ou n ≤ 10,
desastreux sinon.

4.5 Module bisect

Fonction Complexite Cas d’usage

bisect_left(a,
O(log n) Premiere position ≥ x
x)
bisect_right(a,
O(log n) Premiere position > x
x)
insort(a, x) O(n) Insertion ordonnee (rare)
from bisect import bisect_left, bisect_right

left = bisect_left(a, x)
right = bisect_right(a, x)
count_x = right - left

4.6 Module heapq

Fonction Complexite Cas d’usage

heappush(h, x) O(log n) Inserer

heappop(h) O(log n) Extraire le minimum
heapify(arr) O(n) Transformer une liste en heap
nlargest /
O(n log k) Top k
nsmallest
import heapq

h = []
[Link](h, 5)
[Link](h, 2)
smallest = [Link](h)

# max-heap simule
[Link](h, -x)
max_value = -[Link](h)

5 Snippets prets a copier

5.1 Maths
5.1.1 PGCD et PPCM
from math import gcd

def lcm(a, b):

return a // gcd(a, b) * b

Usage : divisibilite, fractions, synchronisation de periodes.

5.1.2 Factorielle simple et precompute

from math import factorial

Version concours 13/26

Competitive Programming en Python Handbook hors ligne

# pour un seul calcul

ans = factorial(n)

# pour beaucoup de requetes modulo mod

fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % mod

5.1.3 Puissance rapide / exponentiation modulaire

def mod_pow(a, b, mod):
res = 1
a %= mod
while b:
if b & 1:
res = res * a % mod
a = a * a % mod
b >>= 1
return res

# ou simplement
ans = pow(a, b, mod)

5.1.4 Test de primalite simple

from math import isqrt

def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
r = isqrt(n)
for d in range(3, r + 1, 2):
if n % d == 0:
return False
return True

5.1.5 Crible d’Eratosthene

def sieve(n):
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
p = 2
while p * p <= n:
if is_prime[p]:
for x in range(p * p, n + 1, p):
is_prime[x] = False
p += 1
return is_prime

5.1.6 Facteurs premiers

def prime_factors(n):
f = {}
d = 2
while d * d <= n:
while n % d == 0:
f[d] = [Link](d, 0) + 1

Version concours 14/26

Competitive Programming en Python Handbook hors ligne

n //= d
d += 1 if d == 2 else 2
if n > 1:
f[n] = [Link](n, 0) + 1
return f

5.1.7 Modulo classique et inverse modulaire

mod = 10**9 + 7

# inverse modulaire si mod est premier et a non multiple de mod

inv_a = pow(a, mod - 2, mod)

A retenir
Reflexe standard : mod = 10**9 + 7. Des que les nombres gonflent, reduis reguliere-
ment modulo mod.

5.2 Tableaux / listes

5.2.1 Prefix sums
def prefix_sums(arr):
pref = [0]
for x in arr:
[Link](pref[-1] + x)
return pref

# somme sur [l, r]

pref = prefix_sums(arr)
range_sum = pref[r + 1] - pref[l]

5.2.2 Suffix sums

def suffix_sums(arr):
n = len(arr)
suf = [0] * (n + 1)
for i in range(n - 1, -1, -1):
suf[i] = suf[i + 1] + arr[i]
return suf

5.2.3 Difference array

def range_add(n, queries):
diff = [0] * (n + 1)
for l, r, val in queries:
diff[l] += val
if r + 1 < n:
diff[r + 1] -= val
arr = [0] * n
cur = 0
for i in range(n):
cur += diff[i]
arr[i] = cur
return arr

5.2.4 Max / min avec indice

max_i, max_v = max(enumerate(arr), key=lambda p: p[1])
min_i, min_v = min(enumerate(arr), key=lambda p: p[1])

Version concours 15/26

Competitive Programming en Python Handbook hors ligne

5.2.5 Suppression des doublons

unique_sorted = sorted(set(arr))

# garder l'ordre d'apparition

seen = set()
unique_keep_order = []
for x in arr:
if x not in seen:
[Link](x)
unique_keep_order.append(x)

5.2.6 Compression de coordonnees

def compress(arr):
vals = sorted(set(arr))
pos = {x: i for i, x in enumerate(vals)}
return [pos[x] for x in arr], vals, pos

5.3 Tri et recherche

5.3.1 Tris courants
asc = sorted(arr)
desc = sorted(arr, reverse=True)
by_second = sorted(pairs, key=lambda x: x[1])
by_second_then_first_desc = sorted(pairs, key=lambda x: (x[1], -x[0]))

5.3.2 Modele de binary search sur reponse

def first_true(lo, hi, ok):
while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo

5.3.3 Lower bound / upper bound style Python

from bisect import bisect_left, bisect_right

lb = bisect_left(a, x) # premier indice avec a[i] >= x

ub = bisect_right(a, x) # premier indice avec a[i] > x
occ = ub - lb

5.4 Frequences
5.4.1 Compter les occurrences
from collections import Counter

cnt = Counter(arr)
# cnt[x] = nombre d'occurrences de x

5.4.2 Element le plus frequent

value, freq = Counter(arr).most_common(1)[0]

Version concours 16/26

Competitive Programming en Python Handbook hors ligne

5.4.3 Groupement simple par cle

from collections import defaultdict

groups = defaultdict(list)
for x, y in pairs:
groups[x].append(y)

5.5 Files / piles

5.5.1 Stack avec list
st = []
[Link](x)
last = [Link]()

5.5.2 Queue avec deque

from collections import deque

q = deque()
[Link](x)
front = [Link]()

5.5.3 Pattern BFS

from collections import deque

def bfs(start, adj):

n = len(adj)
dist = [-1] * n
dist[start] = 0
q = deque([start])
while q:
u = [Link]()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
[Link](v)
return dist

5.6 Graphes
5.6.1 Liste d’adjacence
n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
u -= 1; v -= 1
adj[u].append(v)
adj[v].append(u) # retirer si graphe oriente

5.6.2 DFS iteratif

def dfs_iter(start, adj):
seen = [False] * len(adj)
st = [start]
seen[start] = True
while st:

Version concours 17/26

Competitive Programming en Python Handbook hors ligne

u = [Link]()
for v in adj[u]:
if not seen[v]:
seen[v] = True
[Link](v)
return seen

5.6.3 DFS recursif

import sys
[Link](1_000_000)

def dfs(u, p, adj, seen):

seen[u] = True
for v in adj[u]:
if v != p and not seen[v]:
dfs(v, u, adj, seen)

5.6.4 Composantes connexes

def connected_components(adj):
n = len(adj)
seen = [False] * n
comps = []
for s in range(n):
if seen[s]:
continue
st = [s]
seen[s] = True
comp = []
while st:
u = [Link]()
[Link](u)
for v in adj[u]:
if not seen[v]:
seen[v] = True
[Link](v)
[Link](comp)
return comps

5.7 Recursion / backtracking

5.7.1 Squelette simple
def backtrack(i):
if i == n:
# traiter une solution
return
# choix 1
backtrack(i + 1)
# choix 2
backtrack(i + 1)

5.7.2 Generation de subsets

cur = []
ans = []

def gen(i):
if i == n:

Version concours 18/26

Competitive Programming en Python Handbook hors ligne

[Link](cur[:])
return
gen(i + 1)
[Link](arr[i])
gen(i + 1)
[Link]()

5.7.3 Permutations
used = [False] * n
cur = []

def permute():
if len(cur) == n:
print(cur)
return
for i in range(n):
if used[i]:
continue
used[i] = True
[Link](arr[i])
permute()
[Link]()
used[i] = False

5.8 Programmation dynamique

5.8.1 Template 1D
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] # adapter la recurrence

5.8.2 Template 2D
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

5.8.3 Memoisation avec dictionnaire / lru_cache

from functools import lru_cache

@lru_cache(None)
def solve_state(x, y):
if x == 0:
return y
return solve_state(x - 1, y) + 1

5.9 Strings
5.9.1 Palindrome
def is_pal(s):
return s == s[::-1]

Version concours 19/26

Competitive Programming en Python Handbook hors ligne

5.9.2 Frequences de caracteres

from collections import Counter
cnt = Counter(s)

5.9.3 Sous-chaines / toutes fenetres de longueur k

subs = [s[i:i + k] for i in range(len(s) - k + 1)]

5.10 Grilles
5.10.1 Parcours 2D et voisins 4 directions
dirs4 = [(1, 0), (-1, 0), (0, 1), (0, -1)]

for r in range(n):
for c in range(m):
for dr, dc in dirs4:
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m:
pass

5.10.2 Voisins 8 directions

dirs8 = [
(-1, -1), (-1, 0), (-1, 1),
( 0, -1), ( 0, 1),
( 1, -1), ( 1, 0), ( 1, 1)
]

5.10.3 BFS sur grille

from collections import deque

def bfs_grid(sr, sc, grid):

n, m = len(grid), len(grid[0])
dist = [[-1] * m for _ in range(n)]
dist[sr][sc] = 0
q = deque([(sr, sc)])
while q:
r, c = [Link]()
for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != '#':
if dist[nr][nc] == -1:
dist[nr][nc] = dist[r][c] + 1
[Link]((nr, nc))
return dist

6 Complexites a connaitre

Version concours 20/26

Competitive Programming en Python Handbook hors ligne

6.1 Ordres de grandeur pratiques

Intuition
Complexite Commentaire concours
pratique

O(1) Constant Presque toujours OK

O(log n) Tres rapide Binary search, heap, bisect
O(n) Lineaire OK jusqu’a 106 souvent
Tri / structures
O(n log n) Tres souvent acceptable jusqu’a 2 · 105 ou plus
ordonnees
O(n2 ) Quadratique Souvent OK vers n ≤ 2000, parfois 5000 si leger
O(n3 ) Cubique Reserve aux petits n (100-300)
O(2n ) Exponentiel Seulement pour petits n
O(n!) Permutations Ultra petit n uniquement

6.2 Table rapide selon la taille de n

Taille typique Ce qui passe souvent

n ≤ 20 Backtracking complet, bitmask DP, 2n , parfois n!

n ≤ 30 Meet-in-the-middle, bitmasks, exponential leger
n ≤ 103 O(n2 ) souvent OK, O(n3 ) parfois trop lourd
n ≤ 2 · 105 O(n log n), BFS/DFS, prefix sums, heaps, maps
n ≤ 106 O(n) ou mieux ; attention memoire et I/O
Tres grand
Raisonnement mathematique, greedy, binary search sur reponse, pas
(1012 , 1018 )
de tableau de taille n

Astuce concours
Toujours confronter ton idee a n. Une bonne intuition de complexite fait gagner plus de
temps qu’une parfaite maitrise de syntaxe.

Version concours 21/26

Competitive Programming en Python Handbook hors ligne

7 Astuces Python speciales contest

Astuce Pourquoi / comment

Lecture rapide Remplace souvent input par [Link]. Pour du

parsing massif, regarde le template bufferise de la section 2.
Eviter TLE Evite les concat de chaines repetitives ; prefere accumuler les
reponses puis faire un seul join. Fais attention aux boucles
imbriquees inutiles.
Recursion Utilise [Link](...) seulement si necessaire.
Souvent, un DFS iteratif est plus robuste.
Floats Evite-les si des entiers suffisent. Pour comparer des racines ou
verifier des carres, prefere isqrt.
Copies inutiles arr[:] copie, sorted(arr) copie, [Link]() modifie en
place. Choisis consciemment.
List vs set vs dict list pour l’ordre et les indices ; set pour l’appartenance ; dict
pour les mappings/frequences.
Quand utiliser
Quand tu comptes juste des occurrences ou veux le plus
Counter
frequent rapidement.
Quand utiliser deque Pour BFS, files, ou fenetres glissantes avec pops a gauche.
Quand utiliser heapq Priorites, Dijkstra, top-k, fusion de flux tries.
Indices Verifie toujours si l’entree est 1-indexee. En Python, tout ton
tableau est 0-indexe par defaut.
Cas limites Pense aux tableaux vides, n=1, toutes valeurs egales, chaine
vide, graphe non connexe, bornes negatives.
Precompute Si tu reponds a beaucoup de requetes, precompute (prefix,
fact, sieve) plutot que recalculer.

8 Pieges frequents
Erreurs frequentes
Off-by-one. Les intervalles Python sont souvent de la forme [l:r). range(n) va de 0 a
n-1. pref[r+1] - pref[l] donne la somme sur [l, r].

Erreurs frequentes
Mutation inattendue des listes. mat = [[0]*m]*n est faux pour une vraie matrice
modifiable. Toutes les lignes sont la meme reference.

Erreurs frequentes
Tri en place vs copie. [Link]() modifie arr ; sorted(arr) renvoie une nouvelle
liste. N’ecris jamais arr = [Link]().

Erreurs frequentes
append() vs +. [Link](x) ajoute un element en O(1) amorti. arr = arr + [x]
cree une nouvelle liste et coute plus cher.

Erreurs frequentes
Oublis de conversion. input() renvoie une chaine. "2" + "3" = "23", pas 5.

Version concours 22/26

Competitive Programming en Python Handbook hors ligne

Erreurs frequentes
Input lent. Pour les grosses entrees, input() peut suffire... jusqu’au moment ou non.
Reflexe concours : input = [Link].

Erreurs frequentes
Recursion depth exceeded. Les arbres / graphes profonds cassent vite la recursion
par defaut. Pense a l’iteratif.

Erreurs frequentes
Modulo et divisions. En modulaire, a / b n’a pas de sens. Il faut l’inverse modulaire
de b. En Python, le modulo avec nombres negatifs suit la convention Python.

Erreurs frequentes
remove, discard, pop. remove(x) supprime x et plante si absent ; discard(x) ne plante
pas ; pop() retire un element arbitraire d’un set ou le dernier d’une liste.

Erreurs frequentes
Dictionnaires. Acceder a d[x] sans verifier que x existe peut lever KeyError. Pour du
comptage, prefere [Link](x, 0).

9 Mini bibliotheque personnelle de contest

import sys
from math import gcd, isqrt
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect_right
from functools import lru_cache
import heapq

input = [Link]
mod = 10**9 + 7

def lcm(a, b):

return a // gcd(a, b) * b

def is_prime(n):
if n < 2:
return False
if n % 2 == 0:
return n == 2
for d in range(3, isqrt(n) + 1, 2):
if n % d == 0:
return False
return True

def sieve(n):
is_p = [True] * (n + 1)
is_p[0] = is_p[1] = False
for p in range(2, isqrt(n) + 1):
if is_p[p]:
for x in range(p * p, n + 1, p):
is_p[x] = False
return is_p

def mod_pow(a, b, mod=mod):

return pow(a, b, mod)

Version concours 23/26

Competitive Programming en Python Handbook hors ligne

def prefix_sums(arr):
pref = [0]
for x in arr:
[Link](pref[-1] + x)
return pref

def binary_search_first_true(lo, hi, ok):

while lo < hi:
mid = (lo + hi) // 2
if ok(mid):
hi = mid
else:
lo = mid + 1
return lo

def bfs(start, adj):

dist = [-1] * len(adj)
dist[start] = 0
q = deque([start])
while q:
u = [Link]()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
[Link](v)
return dist

def dfs_iter(start, adj):

seen = [False] * len(adj)
st = [start]
seen[start] = True
while st:
u = [Link]()
for v in adj[u]:
if not seen[v]:
seen[v] = True
[Link](v)
return seen

def factorial_precompute(n, mod=mod):

fact = [1] * (n + 1)
inv_fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % mod
inv_fact[n] = pow(fact[n], mod - 2, mod)
for i in range(n, 0, -1):
inv_fact[i - 1] = inv_fact[i] * i % mod
return fact, inv_fact

def nCr_mod(n, r, fact, inv_fact, mod=mod):

if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % mod * inv_fact[n - r] % mod

A retenir
Cette mini-bibliotheque doit rester courte. L’objectif n’est pas d’avoir 500 lignes, mais
quelques fonctions ultra fiables que tu connais deja.

Version concours 24/26

Competitive Programming en Python Handbook hors ligne

10 Annexe ultra rapide

Objectif
Cette annexe tient lieu de version derniere minute avant contest. Elle concentre
uniquement le plus rentable : syntaxes critiques, fonctions usuelles, snippets reflexes
et reperes de complexite.

A. Syntaxes critiques

Besoin Syntaxe

Lire un entier n = int(input())

Lire deux entiers a, b = map(int, input().split())
Lire une liste arr = list(map(int, input().split()))
Boucle testcases for _ in range(t):
Indice + valeur for i, x in enumerate(arr):
Parcours inverse for x in reversed(arr):
Tri copie / en place sorted(arr) / [Link]()
Dico freq d[x] = [Link](x, 0) + 1
Presence rapide x in set_or_dict
Somme intervalle pref[r+1] - pref[l]

B. Fonctions a memoriser

Fonction Utilite

len, sum, min, max, abs Base absolue

sorted, [Link] Tri
pow(a, b, mod) Puissance modulaire
gcd, lcm Maths concours
Counter, defaultdict,
Frequences / BFS
deque
bisect_left,
Lower / upper bound
bisect_right
heappush, heappop Priorites

C. Snippets reflexes
# lecture rapide
import sys
input = [Link]

# prefix sums
pref = [0]
for x in arr:
[Link](pref[-1] + x)

# BFS
q = deque([src])
while q:
u = [Link]()

# binary search
while lo < hi:
mid = (lo + hi) // 2

Version concours 25/26

Competitive Programming en Python Handbook hors ligne

D. Complexites reperes

Taille Reflexe

n ≤ 20 backtracking / bitmask OK
n ≤ 103 quadratique souvent OK
n ≤ 2 · 105 vise O(n log n) ou mieux
n ≤ 106 lineaire + I/O rapide

E. Checklist de debut de probleme

1. Quelle est la taille max de n ?
2. Les entrees sont-elles 0-indexees ou 1-indexees ?
3. Ai-je besoin d’un set, d’un dict, d’un deque, d’un heap ?
4. Puis-je precompute quelque chose ?
5. Quels sont les cas limites evidents ?

A retenir
Dernier rappel : en contest, la meilleure solution est souvent la plus simple qui passe.
Si une approche O(n log n) propre existe, elle vaut mieux qu’une gymnastique Python
obscure.

Version concours 26/26