[Explication AtCoder] Contrôle ABC158 Problèmes A, B, C avec Python!
Nous expliquerons comment résoudre les problèmes A, B, C du ** AtCoder Beginners Contest 158 ** avec ** Python 3 ** aussi soigneusement que possible pour les débutants.
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 pas à penser à rien --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 le temps restant pour le problème D augmente.
Données ABC158
Date: 2020-03-07 (sam) 21:00 ~ 2020-03-07 (sam) 22:40 (100 minutes) A Nombre de personnes ayant posé des questions: 7053
| Performance | AC | temps | Classement | Ligne directrice |
|---|---|---|---|---|
| 400 | ABC- | 63 minutes | 4580e | Thé performance |
| 600 | ABC- | 23 minutes | 3766e | Taux brun à 8 fois |
| 800 | ABCD | 90 minutes | 2911e place | Performance verte |
(Référence) I: Performance 1144 ABCD-- 44:24 (1WA) 1644e place </ font>
- Un problème (6954 personnes AC)
- La capacité de lecture est testée.
- problème B (5837 AC)
- C'est difficile. C'est facile à comprendre si vous l'écrivez sur papier.
- problème C (5456 personnes AC)
- C'est facile si vous réalisez que vous pouvez faire une recherche complète (round-robin) à 1 yen à partir du plus petit.
- Problème D (3533 personnes AC) [Non expliqué dans cet article] La simulation de l'opération
- est trop tardive.
ABC158A 『Station and Bus』
** Page de problème **: A --Station et bus ** Difficulté **: ★ ☆☆☆☆ ** Point **: opération de chaîne
Même si je ne lis que l'énoncé du problème, je ne sais pas quoi faire. Dans un tel cas, il est bon de voir un exemple concret avec un échantillon pour le moment.
Énoncé du problème
<détails> Il y a une chaîne de trois lettres $ S $ avec seulement "" A " Les gares des différentes sociétés d'exploitation ont des itinéraires différents, le transport n'est donc pas pratique. J'ai donc décidé d'exploiter un bus entre les gares de la société A et de la société B. Cependant, il n'y a pas toujours une combinaison de stations où les bus circulent réellement. Plus précisément, si les trois gares de la ville sont des gares de la même entreprise, il n'y aura pas d'ensemble de gares exploitées par des bus. Déterminez si le bus fonctionne réellement. Vous n'êtes pas obligé d'utiliser votre imagination aux niveaux ci-dessus pendant le concours, mais imaginer et écrire des situations spécifiques peut vous aider à comprendre. S'il y a deux types de $ S $, tels que Puisque le nombre de caractères est fixé à 3, il est facile de taper directement «AAA» et «BBB». Veillez à ne pas confondre «Non» et «Oui» et à les inverser. Si vous vous assurez que l'échantillon passe à chaque fois avant de le soumettre, vous perdrez par inadvertance le WA. Si le nombre de caractères n'est pas fixe, par exemple 1 million de caractères et que vous ne pouvez pas taper directement, il est bon de créer une chaîne de caractères avec le code suivant. Ou vous pouvez utiliser ABC158B『Count Balls』 ** Page de problème **: B --Count Balls
** Difficulté **: ★★★★★
** Point **: Entier (quotient et reste de la division), montant du calcul C'est le plus haut niveau de difficulté en tant que problème B. L'opération de 10 à la 100e puissance de la phrase problème, le maximum de la contrainte est de 10 à la 18e puissance, et un nombre incroyablement énorme en sort. Les humains ne peuvent pas spécifiquement imaginer un si grand nombre. Si vous essayez, ce sera déroutant, alors traitez-le de manière mécanique et abstraite. Si vous lisez l'énoncé du problème et y réfléchissez un instant, vous pouvez voir que le 10 à la 100e puissance signifie «substantiellement infini» et «assez grand», et le nombre lui-même n'a aucune signification. <détails> Faites une rangée infiniment longue de boules en alternant les boules bleues $ bleues et les boules rouges $ rouges. Spécifiez $ N $ dans la plage> 1 ou plus et 100 kyo (= 10 000 fois 100 000 milliards) ou moins. Combien de boules bleues sur $ N $ depuis le début de la rangée de boules? Bien sûr, si vous simulez l'opération avec une boucle while, vous obtiendrez la réponse. Cependant, le problème est que $ N $ peut aller jusqu'à 100K. Même si vous utilisez un PC, le calcul prendra des années, voire des décennies, sans exagération, vous devez donc le trouver par une autre méthode. Quant à la marche à suivre, vous pouvez calculer d'un seul coup en utilisant la "Division des entiers" (division avec restes effectuée dans les classes intermédiaires de l'école élémentaire). Si vous pensez à "l'opération consistant à ajouter des boules bleues $ bleues et des boules rouges $ rouges" comme un ensemble, vous pouvez calculer par division. Reformulons un peu l'opération. Considérez l'opération consistant à ajouter "un cylindre contenant des boules bleues $ bleues et des boules rouges $ rouges" à la ligne une à une. Cependant, si l'ajout du cylindre tel quel et que le nombre de boules dans la rangée dépasse $ N $, nous retirerons les boules une à une du cylindre et les ajouterons à la rangée. A ce moment, la boule bleue sort en premier du cylindre. Oubliez la couleur des boules, et trouvez le nombre $ Q $ de cylindres contenant $ (bleu + rouge) $ boules et le nombre $ R $ de boules libres. Une fois que vous savez cela, vous pouvez facilement calculer le nombre de boules bleues. "Nombre de cylindres $ Q $" et "Nombre de boules roses $ R $" signifie "nombre total de boules $ N $" et "nombre de boules par cylindre $ (Bleu + Rouge) $" Il est calculé en divisant par. Le "nombre total de boules bleues" que vous voulez trouver est "nombre total de boules bleues dans le cylindre" + "nombre de boules bleues de roses", vous pouvez donc calculer et ajouter chacune d'elles. Il y a des boules bleues $ bleues dans un cylindre. Par conséquent, il y a des boules bleues $ Blue \ times Q $ dans un tube de livre $ Q $. Puisqu'un seul tube peut être ouvert, le nombre maximum de boules bleues sur $ R $ boules roses est $ Blue $. En d'autres termes, il s'agit essentiellement de $ R $, mais si $ R $ dépasse $ Blue $ comme le montre l'image ci-dessous, ce devrait être $ Blue $. En d'autres termes, le plus petit de $ R $ et $ Blue $, $ min (Blue, R) $. D'après ce qui précède, le nombre de balles requis est
$ {N} \ div {(Bleu + Rouge)} = Q Si R $ est trop Sera. Écrivons ceci dans le code. Pour les problèmes simples, le nom de la variable peut être une seule lettre "a", "b" ou "x", mais pour les problèmes complexes, il est préférable d'avoir un nom qui vous indique la variable. J'ai cherché et j'ai écrit que le mot anglais pour quotient est "quotient". C'est une perte de temps de chercher pendant le concours, vous pouvez donc utiliser "sho" ou "amari" en lettres romaines. ABC158C『Tax Increase』
** Page de problème **: C - Augmentation de la TVA
** Difficulté **: ★★ ☆☆☆
** Point **: Comment rechercher tout (rond), gérer les boucles et tronquer C'est une question de taxe à la consommation. Je pense que c'est plus facile que le problème B car c'est facile à imaginer concrètement et ce n'est pas difficile à mettre en œuvre. <détails> Étant donné que la limite supérieure de la taxe à la consommation est aussi petite que 100 yens, il semble bon de la vérifier par une recherche complète (round robin). En ce qui concerne la fourchette spécifique, si la taxe à la consommation est de 100 yens, le prix hors taxe est de 1250 yens à 1262 yens s'il est de 8%, et de 1000 yens à 1009 yens s'il est de 10%, vous pouvez donc vérifier 1 yen chacun de 0 yens à 1009 yens. est. Vous n'avez pas à demander cette limite supérieure de 1009 yens. Il est difficile de le demander et cela provoque des erreurs, il est donc facile et sûr de vérifier jusqu'à environ 10 000 yens. Je n'ai besoin que de trouver la valeur minimale, alors je l'augmente de 1 yen et quand je la trouve, j'essaye de sortir de la boucle. Cette fois, j'ai utilisé la fonction intégrée fonction int pour le traitement de la troncature, mais `de l'étage d'importation mathématique Vous pouvez également écrire ʻet utiliser la fonction de sol du module mathématique. Les deux se comportent différemment pour les nombres négatifs, mais ils ne sont pas pertinents pour ce problème.
Recommended Posts
Pour le dire simplement
ou" B "`. Il s'agit d'une chaîne représentant les sociétés d'exploitation des trois stations de la ville d'AtCoder. Par exemple, dans le cas de «ABA», la station 1 et la station 3 sont exploitées par la société A et la station 2 est exploitée par la société B.Comment résoudre
Étape 1: décrypter l'énoncé du problème
" ABA " " ABB ", " A " et " B ", alors " Oui ". Si $ S $ n'a qu'un seul caractère, c'est-à-dire «AAA» ou «BBB» «, c'est« Non ».code
s = input()
if s == "AAA" or s == "BBB":
print("No")
else:
print("Yes")
s = input()
n = len(s) #s longueur n
a_only = "A" * n #Une chaîne suivie de n caractères
b_only = "B" * n #Une chaîne dans laquelle B continue pendant n caractères
if s == a_only or s == b_only:
print("No")
else:
print("Yes")
len (set (s)). Je ne vais pas l'expliquer cette fois, mais il est utile de s'en souvenir.s = input()
num = len(set(s)) #Si vous convertissez en type défini, la duplication disparaît, vous pouvez donc voir le nombre de types avec len
if num == 1:
print("No")
else:
print("Yes")
Énoncé du problème
Pour le dire simplement
Comment résoudre
Étape 1: Notez que la boucle est contrainte et non dans le temps
Étape 2: Réfléchissez à la façon de calculer par formule
{N} \div {(Blue + Red)} =Q trop R
Nombre total de boules bleues dans le cylindre
Nombre de boules bleues de roses
Nombre total
code
n, blue, red = list(map(int, input().split()))
# n / (blue + red) = quot ... rem
quot = n // (blue + red) #Quotient commercial
rem = n % (blue + red) #Reste résiduel
ans = blue * quot + min(blue, rem)
print(ans)
Énoncé du problème
Choses à faire
Étape 1: Réfléchissez à la façon de demander
code
a, b = list(map(int, input().split()))
ans = -1 #Si vous ne trouvez pas la réponse-Réglez 1 sur la valeur initiale
#Vérifier en augmentant de 1 yen de 0 yen à 9999 yens
for price in range(10000):
#8 taxe à la consommation%Et 10%Calculez chacun
tax_a = int(price * 0.08)
tax_b = int(price * 0.1)
#Lorsque la condition est remplie, assignez-la à la réponse et quittez la boucle
if tax_a == a and tax_b == b:
ans = price
break
#Si la réponse est trouvée, la valeur à ce moment-là, si non trouvée, la valeur initiale-1 s'affiche
print(ans)