[GO] 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.

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.