4 méthodes pour compter le nombre d'occurrences d'entiers dans un certain intervalle (y compris la méthode imos) [implémentation Python]

Contexte

Quand je résolvais le problème ABC127 C de la programmation de compétition AtCoder, j'ai pensé au nombre de parties communes qu'il y a dans un ensemble d'entiers consécutifs. Je l'ai trouvé très intéressant car il y avait différentes solutions au problème, j'ai donc décidé d'écrire un article. Le problème peut être trouvé sur le lien ci-dessous. Nous expliquons également le problème ABC127 C, alors faites attention aux spoilers.

AtCoder Beginner Contest 127 C - Prison

C - Prison Commençons par l'énoncé du problème.

スクリーンショット 2020-07-31 2.49.32.png

Rédigez un aperçu de l'énoncé du problème. Il y a des portes M et vous avez besoin d'une carte d'identité pour les ouvrir. Il existe N cartes d'identité, numérotées de 1 à N. Certaines portes ne peuvent ouvrir que des cartes d'identité avec des numéros supérieurs à Li et inférieurs à Ri. Il s'agit de compter le nombre de cartes d'identité qui peuvent ouvrir toutes les portes.

Tout d'abord, considérons un exemple d'entrée. Il y a quatre cartes d'identité, numérotées chacune 1, 2, 3 et 4. Il y a 3 portes, la 1ère porte peut être ouverte avec 1, 2 et 3 cartes d'identité et la 2ème porte peut être ouverte avec 2, 3 et 4 cartes d'identité. Vous pouvez voir que seules 2 et 3 cartes d'identité peuvent ouvrir toutes les portes. En d'autres termes, l'idée était de prendre un jeu de cartes d'identité qui pourraient ouvrir toutes les portes.

Considérer un ensemble à l'aide de la stratégie d'ensemble 1

En conclusion, cette méthode a pris beaucoup de temps de calcul et est devenue TLE et n'a pas réussi.

En tant que politique, les informations de valeur minimale et de valeur maximale du numéro de carte d'identité qui peut ouvrir une porte sont entrées sur une ligne, créez donc le nombre de la valeur minimale à la valeur maximale de la plage et en faire un type défini Converti en. L'opération a été effectuée pour toutes les portes, et l'ensemble de produits a été pris pour tous les ensembles.

Considérez la cause de TLE. Étant donné que le nombre maximum de cartes d'identité pouvant ouvrir une porte est de $ {10 ^ {5}} $, les données $ {10 ^ {5}} $ sont converties à chaque fois, et M (maximum) Vous pouvez voir que le faire pour la porte $ {10 ^ {5}} $) est très coûteux en calcul. Puisque le travail est fait M fois, j'ai estimé que cela coûterait environ $ {O (NM)} $ dans le pire des cas. En raison de la contrainte, le montant du calcul est devenu TLE à $ {O (10 ^ {10})} $.

Je vais mettre le code python pour référence.

python


n, m = map(int, input().split())
line = set(range(1, n + 1))

for i in range(m):
    l, r = map(int, input().split())
    line &= set(range(l, r + 1))

print(len(line))

Politique 1 révisée Politique 2

Lors de l'examen d'un ensemble, cela peut être efficace dans les situations où les cartes d'identité ne sont pas continues, mais dans ce cas, la quantité de calcul était importante et elle n'a pas été efficace. Vous pouvez voir que le montant du calcul doit être au maximum de $ {O (N)} $.

Si vous repensez à la politique, les données sont continues, donc si vous enregistrez le plus grand numéro de carte d'identité parmi la carte d'identité minimum Li et le nombre minimum parmi les Ri maximum, le nombre entre eux sera le même. Je pensais que c'était le numéro.

J'ai réalisé que le contexte de cette politique est venu en arrangeant les numéros sur la carte d'identité qui ouvre les portes pour chaque porte. Dans ce cas, les cartes d'identité sont saisies en continu, cette méthode convient donc. Ri --Li + Peut être ouvert avec une carte d'identité.

Cependant, à titre de mise en garde, si les plages de cartes d'identité ne se chevauchent pas, la valeur de Ri --Li + 1 sera négative, donc si elle est négative, il n'y a pas de carte d'identité qui satisfait à la condition, implémentez donc la sortie 0. Doit être.

python


n, m = map(int, input().split())
l_max = 1
r_min = 10 ** 5

for i in range(m):
    l, r = map(int, input().split())
    l_max = max(l, l_max)
    r_min = min(r, r_min)

print(max(0, r_min - l_max + 1))

J'ai pu obtenir AC avec ce code. Je suis satisfait de cela si je prends simplement AC, mais quand je regardais la diffusion du commentaire, il y avait un commentaire disant qu'il avait été résolu par la méthode imos, alors je me suis intéressé et j'ai reconsidéré une autre solution.

Politique 3 avant d'entrer dans la méthode imos

Avant de travailler sur la méthode imos, j'aimerais envisager une méthode similaire à la méthode imos. Pour conclure d'abord, je pense que cette méthode demande beaucoup de calculs et aboutit à TLE. Notre méthode imos résout ce problème.

Organisons nos pensées. Compte tenu du nombre de portes que les cartes d'identité peuvent ouvrir, le nombre de cartes d'identité qui peuvent ouvrir toutes les portes est de M car n'importe quelle porte peut être ouverte. S'il est inférieur à M, certaines portes ne peuvent pas être ouvertes. En d'autres termes, vous pouvez compter le nombre de cartes d'identité qui peuvent ouvrir les portes M.

Ensuite, je voudrais le mettre en œuvre. Tout d'abord, préparez une matrice pour stocker le nombre de portes que le numéro de carte d'identité peut ouvrir. J'ai préparé un tableau appelé cardid_2_num_map. Le nombre d'éléments est supérieur de un à la valeur maximale de la carte d'identité. L'intention est que le nombre entré soit 1 ou plus et N ou moins, j'ai donc essayé de réduire l'erreur en l'utilisant tel quel lors de la spécification de l'index. Le 0ème tableau n'est jamais utilisé.

Lors de l'examen d'un tableau dont le numéro d'identification de la carte est un index de 0 à $ {10 ^ 5} $ et dont le contenu contient le nombre de portes que la carte d'identité peut ouvrir, [0, 1, 2, 2, 1 , 0, ...] est le tableau que vous souhaitez obtenir dans le cas de l'exemple d'entrée.

Considérant que pour est dupliqué, il semble que la quantité de calcul soit importante. L'ordre maximum du montant du calcul est $ {O (NM)} $, et ce sera TLE comme lors de l'examen de l'ensemble de produits. La méthode imos résout ce problème. Nous en discuterons dans la section suivante.

python


n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 1)

for i in range(m):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        cardid_2_num_map[j] += 1

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

méthode imos, le rôle principal cette fois, politique 4

Je publierai l'article que j'ai utilisé comme référence.

Laboratoire Imos-Laboratoire imos La méthode imos est un algorithme qui a réussi à réduire la quantité de calcul en utilisant la somme cumulée lors du comptage du nombre d'occurrences de nombres consécutifs et en collectant le traitement compté à chaque fois en un.

Revenons au problème ci-dessus et réfléchissons-y. J'ai compté le nombre de cartes d'identité qui pouvaient ouvrir la porte et mis à jour les valeurs du tableau. L'ordre maximum du montant du calcul est $ {O (NM)} $, qui est TLE. Il semble que cela puisse être résolu si l'ordre peut être supprimé à environ $ {O (M)} $.

Donc, si vous revenez à l'exemple d'entrée, il y a quatre cartes d'identité, numérotées respectivement 1, 2, 3 et 4. Il y a 3 portes, la 1ère porte peut être ouverte avec 1, 2 et 3 cartes d'identité et la 2ème porte peut être ouverte avec 2, 3 et 4 cartes d'identité.

Semblable à la stratégie 3, le numéro d'identification de la carte est 0, 1, 2, 3, 4, ..., $ {10 ^ 5} $ dans l'index, et le contenu du tableau est le numéro que la carte d'identité peut ouvrir la porte. Lorsque vous considérez le tableau conservé, la séquence [0, 1, 2, 2, 1, 0, ...] est la séquence que vous souhaitez obtenir dans le cas de l'exemple d'entrée. Le 0ème index n'est pas utilisé car l'ID de la carte indique 0. La méthode imos est utilisée pour obtenir un tel tableau.

Tout d'abord, initialisez le tableau avec des éléments $ {10 ^ 5 + 2} $ et une valeur de 0. L'intention de +2 sera expliquée plus tard. La première porte peut être ouverte avec 1, 2 et 3 cartes, donc le numéro d'index 1 est +1 et le numéro d'index 4 est -1. [0, 1, 0, 0, -1, 0, ..., 0] De même, la deuxième porte peut être ouverte avec 2, 3 et 4 cartes d'identité, donc le numéro d'index 2 est +1 et le numéro d'index 5 est -1. [0, 1, 1, 0, -1, -1, ..., 0] Puisque -1 est utilisé pour l'index de +1 à l'extrémité droite de la carte d'identité, le nombre d'éléments dans le tableau est ajouté de 1 à $ {10 ^ 5} $ et +2 (+1 a été fait pour correspondre au numéro d'index et à l'entrée. ).

Ensuite, la somme cumulée de ce tableau est prise du numéro d'index 0 jusqu'à la fin. A[i + 1] = A[i] + A[i + 1] tenir. En conséquence, la séquence souhaitée [0, 1, 2, 2, 1, 0, ...] peut être obtenue comme dans la politique 3.

Ensuite, si la valeur maximale du tableau est égale au nombre de portes, il existe des cartes d'identité qui peuvent ouvrir toutes les portes, et le nombre de cartes d'identité avec la valeur maximale est compté. L'ordre maximum du montant du calcul était d'environ $ {O (M)} $, et j'ai pu AC.

python


n, m = map(int, input().split())
cardid_2_num_map = [0] * (10**5 + 2)

for i in range(m):
    l, r = map(int, input().split())
    cardid_2_num_map[l] += 1
    cardid_2_num_map[r + 1] -= 1

for i in range(1, n + 1):
    cardid_2_num_map[i] += cardid_2_num_map[i - 1]

max_sum_num = max(cardid_2_num_map)
count_max_card = cardid_2_num_map.count(max_sum_num)

if max_sum_num == m:
    print(count_max_card)
else:
    print(0)

Considération

En ajoutant +1 à l'index à l'extrémité gauche de la plage que vous souhaitez compter et -1 à l'index à l'extrémité droite +1, il est possible d'ajouter +1 uniquement de l'extrémité gauche à l'extrémité droite au stade de la prise finale de la somme cumulée, et pour toutes les zones. Vous pouvez compter le nombre d'apparitions à la fois.

x <Ne rien faire dans la zone la plus à gauche Extrémité gauche <= x <= La zone d'extrémité droite est incrémentée de +1 Puisque la zone de l'extrémité droite <x ne fait rien

Nous sommes en mesure d'effectuer le comptage prévu.

Cette façon de penser peut être appliquée à plusieurs dimensions et la quantité de calcul peut être réduite, donc je l'ai trouvée très intéressante. Les illustrations de l'article dont j'ai parlé étaient très faciles à comprendre. C'est tout.

Recommended Posts

4 méthodes pour compter le nombre d'occurrences d'entiers dans un certain intervalle (y compris la méthode imos) [implémentation Python]
Comment compter le nombre d'occurrences de chaque élément de la liste en Python avec poids
Comment compter le nombre d'éléments dans Django et sortir dans le modèle
Comment obtenir le nombre de chiffres en Python
Un mémorandum sur la mise en œuvre des recommandations en Python
Comment identifier l'élément avec le plus petit nombre de caractères dans une liste Python?
Une implémentation Python simple de la méthode k-voisinage (k-NN)
Comment utiliser la méthode __call__ dans la classe Python
"Livre pour former la capacité de programmation à se battre dans le monde" Exemple de réponse de code Python --1.2 Compter le nombre des mêmes caractères
Obtenez le nombre d'éléments spécifiques dans la liste python
[Homologie] Comptez le nombre de trous dans les données avec Python
[Python] Programmation pour trouver le nombre de a dans une chaîne de caractères qui se répète un nombre spécifié de fois.
Comment compter rapidement la fréquence d'apparition des caractères à partir d'une chaîne de caractères en Python?
Comptez bien le nombre de caractères thaïlandais et arabes en Python
Comment déterminer l'existence d'un élément sélénium en Python
Comment vérifier la taille de la mémoire d'une variable en Python
Comment vérifier la taille de la mémoire d'un dictionnaire en Python
Une fonction qui mesure le temps de traitement d'une méthode en python
Obtenez le nombre de lecteurs d'articles sur Mendeley en Python
Mettre le processus en veille pendant un certain temps (secondes) ou plus en Python
Compter / vérifier le nombre d'appels de méthode.
[Python] Un programme qui calcule le nombre de chaussettes jumelées
[Python] Comment mettre n'importe quel nombre d'entrées standard dans la liste
Diverses méthodes pour créer numériquement la fonction inverse d'une certaine fonction Introduction
Vérifions la chaîne d'octets en mémoire du nombre flottant flottant en Python
J'ai fait un programme pour vérifier la taille d'un fichier avec Python
Comptez le nombre de fois que deux valeurs apparaissent simultanément dans un élément de type itérateur Python 3
Différentes façons de lire la dernière ligne d'un fichier csv en Python
Comment passer le résultat de l'exécution d'une commande shell dans une liste en Python
Sortie du nombre de cœurs de processeur en Python
Récupérer l'appelant d'une fonction en Python
Pour remplacer dynamiquement la méthode suivante en python
Trouvez le nombre de jours dans un mois
Créez un environnement python pour apprendre la théorie et la mise en œuvre de l'apprentissage profond
Obtenez le nombre de tweets liés à un certain mot-clé à l'aide de l'API Twitter
Sortie sous la forme d'un tableau python
Comment obtenir une liste de fichiers dans le même répertoire avec python
Diverses méthodes pour créer numériquement la fonction inverse d'une certaine fonction Partie 1 Régression polynomiale
[Python] Un programme qui trouve le nombre d'étapes le plus court dans un jeu qui traverse les nuages
Comment vérifier en Python si l'un des éléments d'une liste est dans une autre liste
[Python] Représentation du nombre de plaintes des compagnies d'assurance-vie dans un graphique à barres
Trouvez une ligne directrice pour le nombre de processus / threads à définir sur le serveur d'applications
Une histoire sur la tentative d'introduire Linter au milieu d'un projet Python (Flask)
Vérifiez si la chaîne est un nombre en python
[Python] Un programme qui compte le nombre de vallées
Comptez le nombre de paramètres dans le modèle d'apprentissage en profondeur
Implémentation python de la classe de régression linéaire bayésienne
Obtenir la taille (nombre d'éléments) de Union Find en Python
[Python] Création d'une méthode pour convertir la base en 1 seconde
Pour faire l'équivalent de Ruby ObjectSpace._id2ref en Python
Note Python: Le mystère de l'attribution d'une variable à une variable
Voyons comment compter le nombre d'éléments dans un tableau dans certains langages [Go, JavaScript, PHP, Python, Ruby, Swift]
Obtenir la valeur d'une clé spécifique jusqu'à l'index spécifié de la liste de dictionnaires en Python
[Python] Comment supprimer des lignes et des colonnes dans une table (liste des options de méthode de dépôt)
Comprendre la méthode Metropolitan Hasting (une des méthodes de la méthode Monte Carlo en chaîne de Markov) avec implémentation
[OCI] Script Python pour obtenir l'adresse IP d'une instance de calcul dans Cloud Shell
[Super facile! ] Comment afficher le contenu des dictionnaires et des listes incluant le japonais en Python
Ce qui semble être un modèle pour la partie d'entrée standard du pro de la concurrence en python3