AtCoder ABC161 Ceci est un résumé des problèmes du concours AtCoder pour débutants 161 qui a eu lieu le 04/04/2020 (samedi), en commençant par le problème A et en tenant compte des considérations. La première moitié traite des problèmes jusqu'à ABC. Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Il y a trois cases $ A $, $ B $, $ C $. Chaque case contient un entier. Actuellement, les entiers dans les cases $ A $, $ B $, $ C $ sont respectivement $ X $, $ Y $, $ Z $. Trouvez les nombres entiers dans chacune de ces cases après avoir effectué les opérations suivantes dans l'ordre. ・ Échangez le contenu de la boîte $ A $ et de la boîte $ B $ ・ Échangez le contenu de la boîte $ A $ et de la boîte $ C $
À l'origine, le contenu de la boîte $ A $ va dans la boîte $ B $, le contenu de la boîte C va dans la boîte $ A $ et le contenu de la boîte $ B $ va dans la boîte $ C $. Par conséquent, la boîte $ A $ contient $ Z $, la boîte $ B $ contient $ X $ et la boîte $ C $ contient $ Y $, il est donc possible de sortir dans cet ordre.
abc161a.py
x, y, z = map(int, input().split())
print(z, x, y)
Énoncé du problème Nous avons voté pour les produits de type $ N $. Les marchandises $ i $ obtiennent des votes $ A_i $. Sélectionnez la pièce $ M $ populaire dans cette liste. Cependant, vous ne pouvez pas sélectionner des produits dont le nombre de votes est inférieur à $ \ frac {1} {4M} $ du nombre total de votes. Sortez "Oui" si vous pouvez sélectionner des produits populaires de $ M $, ou "Non" si vous ne pouvez pas les sélectionner.
Dans l'explication, la méthode de tri a été décrite en premier, mais j'ai pensé que la deuxième solution était plus simple. Ce n'est pas grave si vous comptez les produits pour lesquels le nombre de votes obtenus est $ \ frac {1} {4M} $ ou plus du nombre total de votes, et jugez s'il y a plus de $ M $. S'il devient WA, je pense que "moins de ** **" peut être confondu avec ce qui suit, ou si "=" doit ou non être inclus dans l'expression conditionnelle. sum (a_list) est une fonction qui additionne tous les nombres de la liste.
abc161b.py
n, m = map(int, input().split())
a_list = list(map(int, input().split()))
sum_a = sum(a_list)
count = 0
for a in a_list:
if a >= sum_a / (4 * m):
count += 1
if count >= m:
print("Yes")
else:
print("No")
Énoncé du problème Aoki peut effectuer les opérations suivantes sur n'importe quel entier $ x $. Opération: Remplacez $ x $ par la valeur absolue de la différence entre $ x $ et $ K $. Compte tenu de la valeur initiale de l'entier $ N $. Trouvez la valeur minimale de $ N $ qui peut être prise lorsque l'opération ci-dessus est effectuée $ 0 $ ou plus autant de fois que vous le souhaitez pour cet entier.
Il m'a fallu un certain temps pour résoudre ce problème. Pour le moment, je pensais que le minimum $ N $ serait obtenu si je bouclais selon les règles, mais quand j'ai écrit le programme, je ne pouvais pas résoudre 1000000000000000000 1 dans l'exemple d'entrée 3 en 2 secondes et je me suis arrêté un peu. Si vous y réfléchissez bien, si l'entrée $ N $ est grande et $ K $ est petite, vous soustrayerez plusieurs fois, mais pour le moment, il est décidé que vous ferez $ N $ / $ K $ fois, vous pouvez donc soustraire ce montant à la fois. Dans cet esprit, le code suivant a été complété. (Comme je n'ai pas eu le temps d'écrire le code en détail pour celui où le résultat de la soustraction est négatif, si (n --k) est négatif pour le moment, si la valeur absolue de la différence est plus grande que le nombre d'origine, il n'y a pas besoin d'en faire plus, et s'il est plus petit, pour le moment Cela fonctionnait si je mettais à jour la valeur absolue de la différence à n)
abc161c.py
n, k = map(int, input().split())
while(True):
if n - k > 0:
if n // k > 0:
n = n - k * (n // k)
else:
if n - k < n:
n = n - k
else:
break
else:
if abs(n - k) < n:
n = abs(n - k)
else:
break
print(n)
Si c'est un vrai concours, vous pouvez écrire le code ci-dessus, mais j'ai réécrit l'article de synthèse un peu plus simplement en référence à l'explication. L'explication est la suivante.
Commentaire Lorsque $ x $ vaut $ K $ ou plus, il devient $ x-K $ en effectuant l'opération. Autrement dit, en effectuant des opérations $ N / K $ à partir de $ N $, l'entier est le reste de $ N $ divisé par $ K $. Soit $ t $ le reste de $ N $ divisé par $ K $. Si vous opérez sur $ t $, ce sera $ K − t $. Si vous opérez sur $ K − t $, cela revient simplement à $ t $. Autrement dit, seuls $ t $ ou $ K − t $ peuvent être considérés comme une valeur inférieure à $ K $. La réponse est donc la plus petite de $ t $ et $ K − t $, c'est-à-dire le reste de $ N $ divisé par $ K $ et $ K− $ (le reste de $ N $ divisé par $ K $). Le plus petit.
C'est une longue histoire au milieu, mais la conclusion est simple et vous pouvez en utiliser trop pour répondre. Si vous écrivez le code en référence à cela, ce sera comme suit.
abc161c.py
n, k = map(int, input().split())
t = n % k
print(min(t, k - t))
J'ai pu écrire en 3 lignes (rires) C'est évident par rapport à ce que j'ai soumis à l'origine. Je regrette de ne pas avoir réalisé que la formule pour n = n --k * (n // k) que j'ai écrite à l'origine est n = n% k. Si l'explication n'est que des lettres et difficile à comprendre, vous pouvez facilement la comprendre en considérant un exemple numérique concret. La liste de tous les différents modèles rend l'article difficile à lire, alors prenons un exemple typique lorsque n = 1003 et k = 5. Dans ce cas, 1003 à 5 sont d'abord soustraits 200 fois et le résultat est 3. Ce 3 est trop de 1003/5, donc le programme peut obtenir 3 par 1003% 5. Autrement dit, t = 3. Enfin, qui est plus petit, t ou k-t, est k --t = abs (t --k) = abs (3-5) = 2. Par conséquent, dans 3 et 2, 2 est plus petit, donc la réponse est 2.
C'est la fin du premier semestre. La seconde moitié expliquera le problème DEF. Merci d'avoir lu jusqu'à la fin de la première moitié pour le moment. Suite dans la seconde moitié.
Recommended Posts