Compter les sous-rectangles sans bombe à l'aide du principe d'inclusion-exclusion
Énoncé du problème
On dispose d'une grille rectangulaire de taille N par M. Des bombes sont placées sur K cellules distinctes (avec K ≤ 20). Le but est de déterminer le nombre total de sous-rectangles (définis par leurs coordonnnées supérieure gauche et inférieure droite) qui ne contiennent aucune bombe.
Approche par principe d'inclusion-exclus ...
Publié le 29 septembre à 08h00
Implémentation d'un arbre de Fenwick bidimensionnel pour les requêtes de somme sur grille
La gestion dynamique de points sur un maillage et le calcul du nombre d'éléments actifs à l'intérieur d'une zone rectangulaire relèvent de problèmes classiques en algorithmique. Lorsque les mises à jour ponctuelles et les requêtes d'intervalle sont fréquentes, la structure de données optimale est l'arbre de Fenwick bidimensionnel (Binary Indexe ...
Publié le 3 septembre à 05h45
Analyse et résolutions des problèmes de la AtCoder Regular Contest 101
Problème C : Candles
Dans ce problème, nous avons $N$ bougies disposées sur une ligne et nous devons en allumer $K$ en partant de l'origine (position 0). Le chemin optimal pour allumer $K$ bougies consécutives sera toujours un segment $[L, R]$ contenant l'origine.
Pour chaque segment possible de $K$ bougies, la distence parcourue est la longueu ...
Publié le 13 juillet à 08h16