Cette page est créée principalement pour les utilisateurs de Python qui estiment que les problèmes A et B du concours AtCoder Beginner (ABC) peuvent être résolus, mais le problème C est difficile, à commencer par AtCoder. Fait. Nous avons brièvement résumé les idées de contraintes et la quantité de calcul, et les idées que vous devez connaître en fonction des contraintes et de la quantité de calcul.
Si vous avez participé à ABC plusieurs fois, vous avez peut-être vu le commentaire avec un ordre de calcul tel que ** $ O (N ^ 2) $ ** et ** $ O (NlogN) $ **. Il peut y avoir. Pour être honnête, même si cela est écrit, il y a beaucoup de gens qui ne comprennent pas ce qu'ils veulent dire ou d'où vient le journal.
Cette idée de commande de montant calculé est la page de ** Kenchon-san **, qui est célèbre dans le monde de la programmation compétitive. ~ D'où vient le journal ~](https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0)
Vous pouvez estimer approximativement à l'avance le temps qu'il faudra pour exécuter le calcul.
Ce sera comme.
Pour une explication détaillée de la commande de montant de calcul, veuillez vous référer à la [page de Kenchon-san] ci-dessus (https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0), mais l'idée de la commande de montant de calcul est la vitesse de calcul. Peut être estimé et deviendra important après le problème C d'ABC (en particulier en Python). Pensons grossièrement à la quantité de calcul.
Pour expliquer brièvement le montant du calcul, ** "Au fur et à mesure que la taille d'entrée ** $ n $ ** augmente, le temps d'exécution augmentera proportionnellement de ce montant." ** Cela devient un index.
Considérons d'abord les problèmes suivants avec des exemples concrets.
Takahashi, élève de première année du primaire qui aime ajouter des chiffres, ajoute toujours 1 + 2 + 3 ... À un moment donné, Takahashi a décidé d'ajouter des entiers de 1 à ** $ n $ **. Quelle est la somme des entiers de 1 à ** $ n $ **?
Ce problème peut être résolu en ajoutant simplement 1 à ** $ n $ **. L'écriture réelle est la suivante.
python
n = int(input())
ans = 0
for i in range(1, n+1):
ans += i
print(ans)
Pensons maintenant à la quantité de calcul dans ce code, mais c'est simple. Le montant du calcul est considéré comme ** $ O (N) $ ** car "1 + 2 + ..." et le nombre de pas ** $ n $ ** ont été effectués. Cela signifie qu'à mesure que la taille d'entrée ** $ n $ ** augmente, le nombre d'étapes de calcul augmente proportionnellement à ** $ n $ **.
Ensuite, considérons les problèmes suivants.
Takahashi, élève de deuxième année du primaire qui aime multiplier les nombres, en a assez de calculer quatre-vingt-dix-neuf. Par conséquent, Takahashi a créé un nouveau quatre-vingt-dix-neuf avec un nombre naturel arbitraire ** $ n $ ** et des carrés verticaux / horizontaux ** $ n $ × $ n $ **. Le nouveau quatre-vingt-dix-neuf a des étapes de 1, 2 ... ** $ n $ ** -1, ** $ n $ ** dans les deux directions verticale et horizontale. Le nombre est 11 × 10 et est ** 110 **. Takahashi-kun, qui a fait le nouveau quatre-vingt-dix-neuf, s'est souvenu qu'il aimait aussi ajouter, alors il a décidé d'ajouter tous les nombres dans le tableau. Quelle est la somme?
Ce problème peut être résolu en utilisant l'instruction for dans l'instruction for. L'écriture réelle est la suivante.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
ans += i * j
print(ans)
Compte tenu du montant de calcul de ce code, il devient ** $ O (N ^ 2) $ **. L'utilisation d'une instruction for dans cette instruction for est appelée une double boucle, et le flux de mouvement est
python
# n = 100
# i =Quand 1
ans += 1 * 1
ans += 1 * 2
ans += 1 * 3
Et quand la deuxième boucle est terminée
python
# n = 100
# i =Quand 1
ans += 1 * 99
ans += 1 * 100
# i =Devenir 2
ans += 2 * 1
ans += 2 * 2
... et continuez jusqu'à i = 100, j = 100. De cette façon, le nombre d'étapes prend ** $ n × n $ ** fois, donc compte tenu du montant du calcul, À mesure que la taille d'entrée ** $ n $ ** augmente, le nombre d'étapes de calcul augmente proportionnellement à ** $ n ^ 2 $ **, ce qui donne ** $ O (N ^ 2) $ **.
Considérons le problème suivant dans ce flux.
Takahashi, élève de troisième année du primaire, a décidé de faire 99 parce que 99 ne suffisait pas. Quatre-vingt-dix-neuf est la somme de la longueur, de la largeur et de la hauteur, et il y a des carrés ** $ n $ × $ n $ × $ n $ **. La longueur, la largeur et la hauteur sont des nombres naturels arbitraires ** $ n $ **, et les étapes sont 1, 2 ... ** $ n $ ** -1, ** $ n $ **, respectivement. Les nombres dans les carrés ** (3, 4, 9) ** sont 3 × 4 × 9, soit ** 108 **. Takahashi-kun, qui a créé le quatre-vingt-dix-neuf, s'est souvenu qu'il aimait aussi ajouter, alors il a décidé d'ajouter tous les nombres dans le tableau. Quelle est la somme?
Ce problème peut être résolu avec une triple boucle qui utilise l'instruction for dans l'instruction for, puis utilise l'instruction for dans celle-ci. L'écriture réelle est la suivante.
python
n = int(input())
ans = 0
for i in range(1, n+1):
for j in range(1, n+1):
for k in range(1, n+1):
ans += i * j * k
print(ans)
Comme vous pouvez le voir, compte tenu de la quantité de calcul dans ce code, il devient ** $ O (N ^ 3) $ **, et si la taille d'entrée ** $ n $ ** augmente, il devient ** $ n ^. Puisque le nombre d'étapes de calcul augmente proportionnellement à 3 $ **, il devient ** $ O (N ^ 3) $ **.
De cette façon, le montant du calcul est ** $ O (N) $ ** pour une instruction pour, ** $ O (N ^ 2) $ ** pour une double boucle et ** $ pour une triple boucle. Si le nombre de boucles augmente comme O (N ^ 3) $ ** ..., la quantité de calcul augmentera à mesure qu'elle augmente.
Au fait, s'il n'y a que deux instructions for au lieu de plusieurs boucles, ce sera ** $ O (N) $ ** au lieu de ** $ O (N ^ 2) $ **. En effet, lorsque l'on considère la quantité de calcul, l'ordre autre que l'ordre le plus grand est supprimé et le coefficient est ignoré. Pour plus de détails, reportez-vous à la page ** Kencho-san ** présentée précédemment.
Ajoutez deux fois les codes 1 à 100 ci-dessous. En fait, ce nombre de pas est de 200 fois, et dans le cas d'une double boucle, 10000 pas sont nécessaires lorsque n = 100, donc on a l'impression de ** $ from ** $ O (N ^ 2) $ ** Je pense que O (N) $ ** est raisonnable.
python
n = 100
ans = 0
for i in range(1, 101):
ans += i
for i in range(1, 101):
ans += i
print(ans)
Maintenant que la quantité de calcul dans l'instruction for est requise, réfléchissons-y avec des contraintes.
Dans le problème réel, la contrainte est toujours écrite comme ci-dessous.
Contraintes ・ ** 1 $ ≤ N ≤ 10 ^ 5 $ **
Avec cette limitation, vous pouvez approximativement comprendre si le code que vous avez écrit respectera le délai en le considérant comme la quantité de calcul.
Par exemple, la contrainte est ・ ** 1 $ ≤ N ≤ 10 ^ 7 $ ** À ce moment-là, cela peut être adopté sans dépasser la limite de temps s'il s'agit d'une instruction for de ** $ O (N) $ **. Cependant, dans le cas de ** $ O (N ^ 2) $ ** comme une double boucle plus grande que ** $ O (N) $ **, le délai sera toujours dépassé. (Parce que le nombre d'étapes pouvant être traitées par seconde est d'environ ** 10 $ ^ 8 $ ** fois)
Au fait, la limite de temps de ABC est de 2 secondes, donc dans le cas de ** $ O (N) $ **, il vaut mieux penser que ** $ N ≤ 10 ^ 7 $ ** est la limite.
Vient ensuite la contrainte ・ ** 1 $ ≤ N ≤ 10 ^ 5 $ ** Ensuite, cela signifie que ** $ O (N) $ ** peut facilement passer, et même un montant de calcul tel que ** $ O (NlogN) $ ** peut être passé dans le délai imparti (plus d'informations à ce sujet plus tard). .. Cependant, dans le cas de ** $ O (N ^ 2) $ **, il ne peut pas être transmis car il dépasse ** $ 10 ^ 8 $ **, ce qui est une ligne directrice.
Et les contraintes ・ ** 1 $ ≤ N ≤ 10 ^ 3 $ ** À ce moment-là, vous pouvez enfin passer le montant de calcul de ** $ O (N ^ 2) $ **.
Il y a aussi des restrictions ・ ** 1 $ ≤ N ≤ 300 $ ** Dans ce cas, vous pouvez également transmettre le montant de calcul de ** $ O (N ^ 3) $ **.
Une fois que vous connaissez la quantité de calcul comme celui-ci, vous pouvez vérifier grossièrement si ce code peut être passé dans la contrainte. Cependant, Python est un langage beaucoup plus lent que d'autres langages tels que C ++, de sorte que les conditions ci-dessus peuvent ne pas s'appliquer. En fait, ABC162-C était un problème de triple boucle, mais la contrainte est ** 1 $ ≤ N ≤ 200 $ **, et le montant du calcul est Le délai peut être dépassé malgré ** $ O (N ^ 3logN) $ **. (Il peut être transmis dans d'autres langues.)
De cette façon, Python doit être plus conscient de la quantité de calcul que les autres langages.
Pensons en fonction du problème réel.
Pensons d'abord à ABC154-C.
Le problème est que, étant donné un tableau d'entiers ** $ n $ **, affiche "OUI" s'il n'y a pas de doublons, et "NON" s'il y a des doublons. Si vous pensez simplement, vous pouvez trouver la réponse en vérifiant chaque tableau un par un en utilisant une double boucle.
python
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
for j in range(i+1, n):
if a[i] == a[j]:
print("NO")
exit()
print("YES")
De cette façon, s'il y a des entiers en double, "NON" est affiché et exit () est utilisé. S'il n'y a pas d'entiers en double, la double boucle se termine et "OUI" est affiché. (Au fait, comme il s'agit d'une double boucle, le montant du calcul est de ** $ O (N ^ 2) $ **)
Mais si vous regardez les limites de ce problème ・ ** 2 $ ≤ N ≤ 200000 $ ** Dans ce cas, ** $ O (N ^ 2) $ ** ne suffit pas.
Ensuite, avec cette contrainte, je pense que le montant du calcul peut être résolu avec ** $ O (NlogN) $ ** ou ** $ O (N) $ **.
Si vous triez le tableau dans l'ordre croissant ou décroissant, s'il y a des nombres en double, ils seront côte à côte, il semble donc que vous serez invité à répondre en vérifiant toutes les valeurs les unes à côté des autres après le tri. En Python, vous pouvez trier le tableau par ordre croissant ou décroissant à l'aide de la méthode sort.
python
a = [5, 2, 3, 4, 3, 9]
a.sort() #ordre croissant
# 2, 3, 3, 4, 5, 9
a.sort(reverse=True) # reverse=Vrai par ordre décroissant
# 9, 5, 4, 3, 3, 2
Puisque le montant du calcul de cette méthode de tri peut être effectué avec ** $ O (NlogN) $ **, le montant du calcul peut être fait avec ** $ O (NlogN) $ ** en vérifiant avec l'instruction for après le tri. (Parce qu'il devient ** $ O (NlogN + N) $ ** et que seul l'ordre le plus élevé est pris en compte)
La version actuelle est la suivante.
python
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(n-1):
if a[i] == a[i+1]:
print("NO")
exit()
print("YES")
De cette façon, si la contrainte est ** $ 10 ^ 5 $ **, il sera plus facile de considérer après le problème C en sachant que ** $ O (N ^ 2) $ ** ne sera pas à temps. Aussi, comme la méthode de tri cette fois, il faudra savoir comment réduire la quantité de calcul.
Ce qui précède est une introduction approximative de l'instruction for, principalement sur le montant du calcul. S'il y a une instruction for dans l'instruction for, le montant du calcul est ** $ O (N ^ 2) $ ** et le montant du calcul de la méthode de tri est ** $ O (NlogN) $ **. Vous ne vous y habituerez peut-être pas au début, mais en pratiquant, vous vous en souviendrez naturellement.
En fonction du problème, il existe de nombreuses façons de réduire la quantité de calcul, telles que la modification de la recherche linéaire en une recherche de deux minutes pour réduire la quantité de calcul, ou la recherche efficace de la somme partielle du tableau par la méthode de saisie ou la somme cumulée. En vous rappelant ces choses, vous serez progressivement en mesure de résoudre le problème C d'ABC.
En tant que moyen de résoudre le problème C d'ABC, je pense que pratiquer beaucoup de questions passées du problème C est la clé de la dévotion. Même si vous faites AC par vous-même, vous pouvez connaître une autre méthode, la quantité de calcul dans ce cas, et comment écrire le code magnifiquement en lisant l'explication ou en lisant le code des autres. Aussi, comme différentes explications sont écrites pour chaque problème, il est difficile de lire l'explication officielle ou le code des autres, alors vérifiez-le et sachez quoi penser.
La fin est devenue désordonnée, mais cet article est terminé. Je vous remercie pour votre travail acharné!
Recommended Posts