AtCoderBeginnerContest170 Review & Summary (premier semestre)

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

Problème A Cinq variables

É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 $.

Problème B Grue et tortue

É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.

  1. Si le nombre total de pattes $ Y $ est supérieur au nombre de pattes lorsque toutes les tortues sont utilisées, "Non"
  2. «Non» si le nombre total de jambes $ Y $ est inférieur au nombre de jambes lorsque toutes sont transformées en grues
  3. Le nombre total de segments ne peut pas être impair, donc si le nombre total de segments $ Y $ est impair, "Non"

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")

Problème C Liste interdite

É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

Problème D non divisible

É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

AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié
AtCoder Revue des questions précédentes (première moitié de 12 / 8,9)