[Explication AtCoder] Contrôle ABC180 Problèmes A, B, C avec Python!

** Les problèmes A, B, C ** du ** AtCoder Beginner Contest 180 ** seront expliqués aussi soigneusement que possible avec ** Python3 **.

Je vise à expliquer une solution qui satisfait les trois points suivants, pas seulement une méthode qui peut être résolue.

--Simple: vous n'avez à penser à rien de plus --Facile à mettre en œuvre: je suis content qu'il y ait moins d'erreurs et de bugs ――Cela ne prend pas longtemps: les performances augmentent et il vous reste plus de temps pour les problèmes ultérieurs.

Si vous avez des questions ou des suggestions, veuillez laisser un commentaire ou Twitter. Twitter: u2dayo

table des matières

[Résumé ABC180](# abc180-Résumé) [Une "boîte à problèmes"](# une boîte à problèmes) [Problème B "Distances diverses"](#b problème distances variables) [Problème C "Chou à la crème"](#c problème à la crème)

Résumé ABC180

Nombre total de soumissions: 5748

performance

Performance AC But temps Classement(Dans les limites)
200 A-C--- 400 Une demi-heure 4393(4250)Rang
400 ABC--- 600 51 minutes 3638(3499)Rang
600 ABC--- 600 23 minutes 3008(2869)Rang
800 ABCD-- 1000 115 minutes 2357(2219)Rang
1000 ABCD-- 1000 62 minutes 1749(1614)Rang
1200 ABCD-- 1000 23 minutes 1241(1110)Rang
1400 ABCDE- 1500 85 minutes 850(724)Rang
1600 ABCDE- 1500 60 minutes 565(441)Rang
1800 ABCDE- 1500 44 minutes 364(251)Rang
2000 ABCDE- 1500 33 minutes 227(131)Rang
2200 ABCDE- 1500 26 minutes 136(63)Rang
2400 ABCDE- 1500 17 minutes 83(29)Rang

Taux de réponse correct par couleur

Couleur Nombre de personnes A B C D E F
Cendre 2412 99.0 % 68.4 % 64.4 % 12.4 % 1.2 % 0.0 %
thé 1093 99.5 % 92.5 % 93.7 % 45.6 % 7.0 % 0.2 %
vert 889 99.9 % 97.6 % 99.0 % 79.0 % 31.6 % 0.1 %
eau 544 100.0 % 99.8 % 99.8 % 95.8 % 73.2 % 0.7 %
Bleu 268 100.0 % 99.6 % 99.6 % 97.8 % 94.0 % 6.3 %
Jaune 109 98.2 % 97.2 % 99.1 % 98.2 % 91.7 % 26.6 %
Orange 26 100.0 % 100.0 % 100.0 % 96.2 % 96.2 % 69.2 %
rouge 8 62.5 % 62.5 % 62.5 % 62.5 % 75.0 % 100.0 %

Bref commentaire

Un problème (5699 personnes AC) "box"
C'est OK si vous écrivez le code pour l'addition et la soustraction.
Problème B (4683 personnes AC) "Diverses distances" Utilisez la boucle
for pour le trouver exactement tel qu'il est écrit.
Problème C (4585 personnes AC) "Chou à la crème"
C'est un problème pour sortir les fractions dans l'ordre croissant. L'énumération des fractions peut être faite avec $ O (N) $.
Problème D (2471 AC) "Takahashi Unvolved" [non expliqué dans cet article] Alors que
$ A $ doit être doublé, multipliez en fait $ A $ pour simuler. Quand il est préférable d'ajouter $ B $, calculez et trouvez le nombre de fois restants. De $ 2 ^ {60}> 10 ^ {18} $, le nombre de fois pour multiplier $ A $ est au maximum de 60 $.
Problème E (1189 personnes AC) "Vendeur ambulant parmi les villes aériennes" [non expliqué dans cet article]
Le coût entre les villes n'est que de 17 $ ^ 2 = 375 $ au maximum, et il est facile à trouver, alors trouvez-le d'abord. Ensuite, cela devient juste un problème de voyageur de commerce. Le problème du voyageur de commerce est $ O (N!) $ Lors de l'essai de tous les itinéraires, mais $ O (N ^ {2} 2 ^ {N}) $ en utilisant la méthode de planification dynamique dite ** bitDP **. Peut être résolu avec.
Problème F (80 personnes AC) "Unbranched" [non expliqué dans cet article]
Cela semble être une méthode de planification dynamique. Comme le nom du problème l'indique, le graphique ne se branche pas.

Résultats de moi (Unidayo) (référence)

screenshot.266.png

Depuis que j'étudie l'information appliquée, c'est une participation virtuelle.

Un problème "boîte"

** Page de problème **: A --box

Considération

Vous n'avez pas à penser au cas où il ne suffit pas d'essayer de récupérer $ A $. C'est parce qu'il n'est pas écrit dans l'énoncé du problème et que la contrainte est $ A \ le {100} \ le {N} $.

Par conséquent, $ N-A + B $ est la réponse.

code

N, A, B = map(int, input().split())
print(N - A + B)

Problème B "Différentes distances"

** Page de problème **: B - Différentes distances

Considération

La formule de calcul de la distance est écrite dans l'énoncé du problème. Même si vous ne comprenez pas la signification de la distance, vous pouvez la calculer exactement telle qu'elle est écrite. (Au fait, il est impossible de penser concrètement à la distance au-delà de la dimension 4 $)

La signification de chaque formule est la suivante.

1. Distance de Manhattan

『 x_iValeur absolue de|x_i|] Est le total (total).

2. Distance euclidienne

La racine carrée de la somme de "$ x_i $ au carré $ {x_i} ^ {2} $". Si vous mettez une valeur négative au carré, elle sera positive, vous pouvez donc supprimer la valeur absolue.

Cela peut sembler difficile à première vue, mais ce sera $ \ sqrt {x ^ 2 + y ^ 2} $ dans le plan de dimension $ 2 $ et $ \ sqrt {x ^ 2 + y ^ 2 + z ^ 2} $ dans l'espace de dimension $ 3 $. .. C'est la distance normale que vous apprenez en mathématiques au collège ou au lycée.

3. Distance de Chebyshev

『x_iValeur absolue de|x_i|] Est la valeur maximale.

la mise en oeuvre

Créez des variables first, second_temp, third avec une valeur initiale de $ 0 $. Correspond à "Manhattan distance", "Euclidean distance square root contents", et "Chevishev distance" dans l'ordre de sortie.

Regardez les éléments de la liste des coordonnées de point «X» dans une boucle for, $ 1 $ chacun, et calculez ces $ 3 $.

Traitement dans la boucle for

Il s'agit du processus effectué dans la boucle for.

Le $ 1 $ ème «distance de Manhattan» est «first + = abs (x)» car vous pouvez ajouter les valeurs absolues.

Le $ 2 $ th "contenu de la racine carrée de la distance euclidienne" est "second_temp + = x ** 2" car il vous suffit d'ajouter le carré.

Le $ 3 $ e "distance de Chevishev" est troisième = max (troisième, abs (x)) car la valeur absolue maximale doit être mise à jour.

Traitement post-boucle

Prenez la "deuxième" route pour trouver la "distance euclidienne". Autrement dit, second = second_temp ** 0.5.

Puisque tout a été demandé, affichez dans l'ordre «premier», «deuxième», «troisième» et la fin.

code

Vous n'avez pas à vous en préoccuper en Python, mais second_temp peut être aussi gros que 10 $ ^ {15} $. En C ++ etc., vous devez faire attention au débordement.

N = int(input())
X = list(map(int, input().split()))

first, second_temp, third = 0, 0, 0

for x in X:
    first += abs(x)
    second_temp += x ** 2
    third = max(third, abs(x))

second = second_temp ** 0.5

print(first)
print(second)
print(third)

prime

Vous n'êtes pas obligé de faire cela, mais vous pouvez également utiliser les fonctions d'ordre supérieur (fonctions qui prennent une fonction comme arguments) map et reduction pour trouver chacune sur une ligne $ 1 $.

#Peut-être qu'il y a une meilleure façon d'écrire
N = int(input())
X = list(map(int, input().split()))

print(sum(map(abs, X)))
print((sum(map(lambda x: x ** 2, X))) ** 0.5)
print(max(map(abs, X)))

Problème C "Chou à la crème"

** Page de problème **: C - Bouffée de crème

Signification du problème

Sortez les fractions de $ N $ dans l'ordre croissant.

Considération

Les choux à la crème peuvent coûter jusqu'à 10 $ ^ {12} $, donc tout essayer de 1 $ à 10 $ ^ {12} $ ne suffit pas.

Soit dit en passant, ** "le nombre de personnes qui peuvent diviser les choux à la crème également sans les diviser" ** signifie ** "le nombre divisible par $ N $" **.

** "Un nombre divisible par un entier $ N $" ** est appelé ** "une fraction de $ N $" **.

** L'énumération des fractions peut être effectuée avec $ O (\ sqrt {N}) $. ** $ \ sqrt {10 ^ {12}} = 10 ^ 6 $, donc c'est dans le temps. (10 $ ^ 6 $ correspondent à 100 millions de dollars)

Méthode efficace de dénombrement des réductions

abc180_c.png

Les propriétés des fractions sont ** "Si vous connaissez toutes les fractions en dessous de $ \ sqrt {N} $, vous pouvez diviser $ N $ par elles pour trouver toutes les fractions au-dessus de $ \ sqrt {N} $" ** il y a.

En profitant de cette propriété, ** "Essayez de diviser réellement $ N $ par $ \ sqrt {N} $, et si elle est divisible, ajoutez $ x $ et $ N / x $ à la liste de réduction" ** , $ O (\ sqrt {N}) $ peut être utilisé pour énumérer les fractions.

Raison détaillée
Supposons que $ N $ ait une fraction de $ x $. A ce moment, $ \ frac {N} {x} $ est toujours une fraction de $ N $.

C'est parce que $ N \ div {\ frac {N} {x}} = N \ fois {\ frac {x} {N}} = x $. Par exemple, $ 36 = 3 \ times {12} $ est une fraction de 36 $ pour 3 $ et 12 $.

Nous appellerons ces $ x $ et $ \ frac {N} {x} $ ** "une paire de fractions" **. ** Une "juste paire" est toujours inférieure ou égale à $ \ sqrt {N} $ et l'autre est supérieure ou égale à $ \ sqrt {N} $. ** **

** S'il y a une fraction supérieure ou égale à $ \ sqrt {N} $, la paire est toujours inférieure ou égale à $ \ sqrt {N} $. Par conséquent, vous pouvez énumérer les fractions en divisant $ N $ par toutes les fractions ci-dessous $ \ sqrt {N} $. ** **

<détails>

Preuve </ summary>
Une "juste paire" prouve toujours que l'un est inférieur à $ \ sqrt {N} $ et l'autre est supérieur à $ \ sqrt {N} $.

Les deux sont supposés être inférieurs à $ \ sqrt {N} $, c'est-à-dire $ x \ lt {\ sqrt {N}} $ et $ \ frac {N} {x} \ lt {\ sqrt {N}} $.

Multiplier l'inégalité

x\times{\frac{N}{x}} < \sqrt{N}\times{\sqrt{N}}\\
N < N

Sera. C'est étrange car $ N = N $. En d'autres termes, l'hypothèse ne peut pas être fausse.

De même, il ne peut y avoir de "tous deux supérieurs à $ \ sqrt {N} $" avec l'inégalité inversée.

D'après ce qui précède, l'une des "justes paires" est toujours $ \ sqrt {N} $ ou moins, et l'autre est $ \ sqrt {N} $ ou plus.

la mise en oeuvre

En gros, tout ce que vous avez à faire est d'écrire le code ci-dessous.

divs = []

x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.append(x)
        divs.append(N // x)
    x += 1

Cependant, il y a des problèmes $ 2 $ avec ce code.

  • ** Lorsque $ \ sqrt {N} $ devient une fraction, $ \ sqrt {N} $ est ajouté à la liste de $ 2 $ **
  1. ** Les résultats ne sont pas par ordre croissant **

Le problème de $ 1 $ seconde peut être résolu en séparant les cas où $ \ sqrt {N} $ est une fraction, mais c'est gênant.

Nous utiliserons ** set type ** pour éviter la duplication. Le type d'ensemble est un type qui gère un «ensemble non ordonné» et ne contient que 1 $ pour le même élément. Si vous ajoutez un élément qui existe déjà, rien ne se passe.

Le problème de $ 2 $ peut être résolu par le tri. Cependant, le type d'ensemble n'a pas le concept d'ordre et ne peut pas être trié. Convertissez en liste, puis triez.

code

N = int(input())
divs = set()  #Utilisez set pour éviter la duplication

#Mathématiquement x<= N ** 0.Identique à 5, mais plus sûr à comparer avec des entiers sans erreur
x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.add(x)  #Ajouter à l'ensemble est ajouter, pas ajouter
        divs.add(N // x)
    x += 1

ans = list(divs)  #Je veux trier par ordre croissant, alors faites une liste et triez
ans.sort()

for x in ans:
    print(x)

Recommended Posts