AtCoder ABC170 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 170 qui a eu lieu le 14/06/2020 (dimanche), en commençant par le problème A et en tenant compte des considérations. Le premier semestre traite des problèmes jusqu'à ABCD. 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 $ 5 $ Il y a deux variables $ x_1, x_2, x_3, x_4, x_5 $. Initialement, la variable $ x_i $ a reçu l'entier $ i $. Sunuke-kun a sélectionné $ 1 $ parmi ces variables et affecté $ 0 $ à cette variable. Vous recevrez la valeur des variables $ 5 $ après que Sunuke-kun ait fait cela. Veuillez répondre à quelle variable Sunuke-kun a attribué $ 0 $.
Pour la soumission, l'instruction for a été tournée afin que la partie avec 0 élément soit sortie. La plupart des langages de programmation commencent par $ 0 $ dans le tableau, donc si vous faites attention à cela, vous ne devriez pas avoir à vous soucier de WA.
abc170a.py
x = list(map(int, input().split()))
for i in range(5):
if x[i] == 0:
print(i + 1)
Après avoir regardé l'explication après avoir terminé, j'ai pensé que la réponse serait 15 $ - x_1 - x_2 - x_3 - x_4 - x_5 $.
Énoncé du problème Il y a des animaux dans le jardin. Ce sont soit des grues avec des jambes de 2 $, soit des tortues avec des jambes de 4 $, respectivement. Takahashi dit: "Le nombre total d'animaux dans le jardin est de X $, et le nombre total de leurs pattes est de Y $." Déterminez s'il existe une combinaison de numéros de grues et de tortues qui rend cette affirmation correcte.
J'ai ajouté les règles avec les déclarations if dans l'ordre que je pensais.
abc170b.py
x, y = map(int, input().split())
if y < 2 * x or x * 4 < y:
print("No")
else:
if y % 2 == 1:
print("No")
else:
print("Yes")
Énoncé du problème Étant donné l'entier $ X $ et la suite d'entiers $ p_1,…, p_N $ de longueur $ N $. Trouvez l'entier (pas forcément positif) non inclus dans la suite d'entiers $ p_1,…, p_N $ qui est le plus proche de $ X $, c'est-à-dire celui qui a la plus petite différence absolue avec $ X $. .. S'il existe plusieurs entiers de ce type, veuillez répondre au plus petit.
Les nombres non inclus dans la chaîne d'entiers ont été recherchés dans l'ordre à partir de l'entrée $ X $. Si $ N $ est grand, ```if x dans la liste: `` `prendra beaucoup de temps, donc je change la liste en dict, mais cette fois $ N $ est petit, donc je l'ai laissé tel quel.
Par exemple, si l'entrée est $ 6 $, la recherche est effectuée dans l'ordre de 6, 5, 7, 4, 8, .... (Le programme a vérifié l'entrée $ x = 6 ± 0 $ deux fois, mais je pensais qu'il n'y aurait pas beaucoup de différence dans le temps d'exécution, donc je l'ai implémenté sous une forme facile à implémenter.)
abc170c.py
x, n = map(int, input().split())
p_list = list(map(int, input().split()))
for i in range(0, n // 2 + 2):
if x - i not in p_list:
print(x - i)
break
if x + i not in p_list:
print(x + i)
break
Énoncé du problème Étant donné une séquence de $ N $ de longueur $ A $. Veuillez répondre au nombre d'entiers $ i (1 \ leq i \ leq N) $ qui satisfont les propriétés suivantes. ・ Pour tout entier $ j (1 \ leq j \ leq N) $ qui est $ i \ neq j $, $ A_i $ n'est pas divisible par $ A_j $
J'ai réfléchi à diverses idées pendant le concours, mais je n'ai pas pu le résoudre. J'ai soumis le code suivant pour "TLE".
abc170dTLE.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
flag_list = [1] * len(sorted_dict)
i = 0
for key, count in sorted_dict:
if flag_list[i] == 0:
i += 1
continue
if count > 1:
flag_list[i] = 0
i += 1
j = i
for key1, count1 in sorted_dict[i:]:
if flag_list[j] == 0:
j += 1
continue
if key1 % key == 0:
flag_list[j] = 0
j += 1
print(sum(flag_list))
Je pensais que la quantité de calcul dans la seconde moitié pourrait être réduite en triant et en voyant si les plus petits pouvaient casser les plus grands, mais ce n'était pas bon.
En fait, il est géré en le mettant dans un ensemble, et $ 2 $ fois, $ 3 $ fois, $ 4 $ fois, ..., $ k $ fois ($ k $ est $ a_i × k \ leq a_ {max) Il semble que cela puisse être résolu en supprimant l'entier maximum $ k $) qui satisfait} $ de l'ensemble. Je ne pouvais pas y penser.
abc170d.py
import collections
n = int(input())
a_list = list(map(int, input().split()))
a_dict = dict(collections.Counter(a_list))
sorted_dict = sorted(a_dict.items(), key=lambda x:x[0])
a_set = set(a_list)
m = max(a_list)
for key, count in sorted_dict:
if key in a_set:
j = key * 2
while j <= m:
a_set.discard(j)
j += key
if count > 1:
a_set.discard(key)
print(len(a_set))
C'est la fin du premier semestre. Personnellement, j'ai baissé les taux ces derniers temps, mais c'est naturel parce que je n'ai pas été en mesure de trouver du temps pour résoudre les questions du passé lors de concours d'analyse de données ou d'écrire des articles. J'ai beaucoup d'études pour le concours, j'aimerais donc le digérer petit à petit (je veux comprendre et mettre en œuvre la méthodologie minimale d'ici le prochain concours). Pour le moment, à tout le moins, je voudrais viser à ABC pour maintenir l'habitude de participer à chaque fois pendant un certain temps. Merci d'avoir lu jusqu'à la fin du premier semestre.
La seconde moitié expliquera le problème EF, mais je ne pense pas pouvoir écrire un article à temps (sueur).
Recommended Posts