Chez Coder (08/09/2020)

AtCoder Beginner Contest 006 Commençons donc par 006 du concours pour débutants AtCoder! (Veuillez garder à l'esprit le sentiment que vous ne devriez pas commencer par 001 ...)

Problème-A

Le nombre N est donné. Sortie OUI si N contient 3 ou est divisible par 3, sinon sortie NON.

A.py


N = int(input())
if N % 3 == 0:
    print("YES")
else:
    print("NO")

Est-ce une version légèrement plus simple du problème FizzBuzz? N'oubliez pas d'insérer un saut de ligne lorsque vous répondez.

Problème-B

Il existe une séquence tribonacci. Cette séquence de nombres est la somme des nombres jusqu'à trois. À proprement parler

a_1=0, a_2=0, a_3=1 \\
a_n=a_{n-1}+a_{n−2}+a_{n−3}

Est défini comme. Trouvez le reste du nième terme de cette séquence, $ a_n $ divisé par 10007.

B.py


n = int(input())
a, b, c = 0, 0, 1

for i in range(n-1):
    a, b, c = (b % 10007), (c % 10007), ((a+b+c) % 10007)
print(a)

Je suis vulnérable à ce genre de problème de division par un grand nombre (comme 10 ^ 7) et d'affichage du reste. Récemment, j'ai pris des mesures pour calculer la réponse finale à chaque fois au lieu de la diviser par un grand nombre. .. Une autre façon de penser à ce problème est de passer à la sortie 0 dans le cas de $ a_1 $ et $ a_2 $, et dans d'autres cas, de tourner une instruction for avec le nombre de boucles égal à n-3. .. (Je vais le télécharger sur git.)

Problème-C

«Il n'y a N humains dans cette ville. Il existe trois types d'humains: les adultes, les vieillards et les bébés. Le nombre total de jambes des humains dans cette ville est de M, deux jambes adultes et des hommes âgés. En supposant 3 jambes et 4 jambes de bébé, répondez à une combinaison possible d'êtres humains. "

C.py


n, m = map(int, input().split())

for a in range(n+1):
  b = 4*n -2*a - m
  c = n -a -b
  if b >= 0 and c >= 0:
    print(a, " ", b, " ", c)
    break
else:
  print("-1 -1 -1")

Il y a plusieurs choses écrites

a+b+c=N \\
2a+3b+4c=M

C'est la même valeur que la résolution des équations simultanées de. Je peux utiliser mes connaissances en mathématiques de manière inattendue, alors je veux faire attention à ne pas m'en débarrasser.

À propos, lorsque j'ai évoqué la méthode de résolution, j'ai vu une fonction xrange au lieu d'une fonction range. Je l'ai vu pour la première fois, alors j'ai trouvé un article comme celui-ci en le recherchant.

Changements de Python 2 à Python 3.0

Je vois, il a été aboli à votre insu. Je ne le savais pas du tout car je l'ai utilisé à partir de python3. Ce serait peut-être une bonne idée de profiter de cette occasion pour étudier les itérateurs.

Problème-D

Il y a N cartes avec des nombres écrits dessus. Les opérations suivantes peuvent être effectuées sur ce lot de cartes (deck). Retirez une carte du jeu et insérez-la n'importe où. De haut en bas du paquet, trouvez le nombre minimum d'opérations nécessaires pour trier les cartes par ordre croissant.

D.py


import bisect

n = int(input())
cards = [int(input()) for i in range(n)]

sort_after_cards = [0]
for card in cards:
  if sort_after_cards[-1] < card:
    sort_after_cards.append(card)
  else:
    index = bisect.bisect_left(sort_after_cards, card)
    sort_after_cards[index] = card    
print(n - len(sort_after_cards) +1)

L'image est comme tirer une carte sur le pont pour en faire un autre. Et pour le faire dans l'ordre croissant, un nombre plus grand que la carte originale doit venir sous le jeu, donc si un nombre plus petit arrive, retournons-le à la position du véritable amour en dichotomisant. Finalement, une liste de deck ascendante sera créée qui exclut les cartes échangées. Si vous souhaitez simplement utiliser l'ordre croissant, vous pouvez utiliser le tri ou le tri.

en conclusion

Pour la première fois, j'ai eu du mal à comprendre. En particulier, j'estime que les problèmes C et D sont nécessaires pour réduire la quantité de calcul et améliorer l'efficacité en utilisant pleinement la pensée mathématique et les algorithmes. Dans les concours récents, je suis en bonne forme et je ne peux résoudre que le problème C, donc je vais beaucoup m'entraîner et essayer de trouver diverses idées.

Recommended Posts

Chez Coder (08/09/2020)
Remplir au codeur
Au Coder # 1 à minuit
[At Coder] Méthode de sortie
[At Coder] ABC128B --Guidebook
[At Coder] Triplés Acing C-XYZ
[Python] Modèle Pro compétitif [Chez Coder]
[At Coder] ABC085C - La réponse Python d'Otoshidama
[At Coder] Débutant Contest 175 Présentation de la solution ABCD python
[Python] ABC133B (problème du triangle supérieur droit) [At Coder]
Étudier à Zundoko
python chez docker
[Chez Coder] Résoudre le problème de la dichotomie
[Python] ABC159D (Mathématiques au lycée nCr) [At Coder]
[Python] AGC043A (problème de lecture et de DP) [At Coder]
[At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]
[Python] [BFS] Au concours de codeur pour débutants 168-D [.. Double Dots]
[Pratique professionnelle de compétition] J'ai essayé chez Coder Beginner Selection