[Entraînement compétitif] J'ai essayé AtCoder Beginner Contest 171

Nous avons participé à AtCoder Beginner Contest 171. C'est la première fois que je participe à un concours de programmation.

3 Complet, le problème D a été bloqué par le mur du temps d'exécution, E a également été implémenté, mais TLE est embarrassant avec un code indescriptible lors de la révision maintenant ...

A - Alphabet

#Alphabet
S = input()
if S in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ':
    print('A')
else:
    print('a')

Problème de retour des majuscules ou des minuscules pour la saisie d'une lettre de l'alphabet. J'aurais aimé pouvoir juger d'après le code ASCII, etc., mais je n'avais jamais implémenté une telle chose en Python, donc comme vous pouvez le voir, j'ai répondu de force.

B - Mix Juice

#Mix Juice
N, K = list(map(int, input().split()))
P = sorted(map(int, input().split()))
print(sum(P[0:K]))

Le prix de chacun des N types de fruits est indiqué, et le prix le plus bas lors de l'achat de l'un des K types de fruits est calculé. ↓ Triez N types de prix et répondez comme la valeur totale de K du plus petit.

C - One Quadrillion and One Dalmatians

#One Quadrillion and One Dalmatians
alphabet = list('abcdefghijklmnopqrstuvwxyz')
N = int(input())-1
 
def shin26(N):
    if(int(N/26)!=0):
        return(shin26(int(N/26)-1)+alphabet[N%26])
    return alphabet[N%26]
 
print(shin26(N))

Une question qui renvoie A à Z, AA à AZ, BA ~ ... pour une entrée comme le numéro de colonne EXCEL (la réponse est inférieure). J'ai changé la fonction récursive pour trouver le nombre N-aire afin qu'il renvoie les chaînes de caractères a à z. Ici aussi, en créant une liste de a à z, l'alphabet peut être obtenu en donnant l'adresse de la liste.

Après cela, j'ai découvert l'opérateur de division de troncature "//" sur Python. (Il n'était pas nécessaire de combiner int et opérateur de division)

D - Replacing

###Échec###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
 
for i in range(Q):
    B, C = list(map(int, input().split()))
    CC = A==B
    NC = CC==False
    A = A*(NC) + C*CC
    print(A.sum())

D Le problème n'a pas pu être résolu à temps. Étant donné un tableau A, le problème du remplacement répété de B par C et de la sortie de la valeur totale de A à chaque fois. Au début, je l'ai remplacé honnêtement, mais il a coulé parce que le temps d'exécution était dépassé.

Il m'a informé que si je connaissais le nombre de Bs dans le tableau immédiatement après la fin, je serais en mesure de trouver la différence par rapport à la valeur totale précédente (Merci!)

###Échec###
#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    if B in u:
        posB = np.where(u==B)
        asum += int(count[posB]) * (C-B)
        # print(u)
        # print(count)
        if not (C in u):
            u[posB] = C
        else :
            posC = np.where(u==C)
            count[posC] += count[posB]
            u = np.delete(u,posB)
            count = np.delete(count,posB)
    print(asum)

Convertissez le tableau A en un tableau avec un nombre u d'un certain nombre. Lors du passage de B à C, le nombre a été changé, et s'il pouvait être intégré, la politique était d'intégrer (la sortie est calculée à partir de la différence comme décrit ci-dessus), mais cela a également coulé.

** La recherche de liste est lente **

Je savais……. Il est lent à activer les instructions sur Python (généralement, s'il y a un calcul à tourner pour les instructions, remplacez-le par une opération de matrice et tournez-le avec numpy). En outre, les connaissances des utilisateurs C ++ ont également subi un dépassement de temps de la même manière.

Un plan pour créer un arbre de conversion B → C et l'appliquer à la fin ↓ Impossible car une sortie est requise pour chaque conversion.

Après tout, jetez un œil au commentaire "Puisque l'entier d'entrée est au plus de 10 $ ^ 5 $, créez un tableau de 10 $ ^ 5 $ et entrez le numéro de ce nombre dans l'adresse de l'adresse." Cela ne nécessite certainement pas de recherche!

Donc, j'ai eu AC avec la réponse suivante.

#Replacing
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
u, count = np.unique(A,return_counts=True)
L = np.zeros(10**5,int)
for i in range(len(u)):
    L[u[i]-1] = count[i]
asum = A.sum()
for i in range(Q):
    B, C = list(map(int, input().split()))
    asum += L[B-1] * (C-B)
    L[C-1] += L[B-1]
    L[B-1] = 0
    print(asum)

E - Red Scarf

###Échec###
#Red Scarf
import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
output = ''
 
def binary(A, p):
    if not np.all(A==0) :
        return binary( (A-A%2)/2 , p+1 ) + ((A%2).sum())%2 * 2**p
    return ((A%2).sum())%2 * 2**p
 
for i in range(N):
    ken = (np.delete(A,i))
    output += str(int(binary(ken,0)))
    if i != N-1:
        output += ' '
 
print(output)

Je ne connaissais pas xor, donc je l'ai jugé par binaire. Fin

J'ai fait cela parce que j'ai compris que cela pouvait être jugé par le nombre de 1 dans chaque chiffre du nombre binaire, mais TLE. J'ai eu un AC ci-dessous avec le conseil d'une connaissance que je pourrais prendre xor de tous les nombres, puis prendre mon propre numéro et xor.

#Red Scarf
N = int(input())
A = list(map(int, input().split()))
output = list()
 
axor = A[0]
for i in range(1,N):
    axor ^= A[i]
 
for i in range(N):
    output.append(axor^A[i])
print(*output)

J'ai ajouté un peu de connaissances mémorisées telles que la méthode d'ajout.

Résumé

Le problème F est intact. Au prochain ABC, nous travaillons dur pour résoudre les questions du passé afin de viser un plus grand nombre de réponses complètes. J'aimerais que cela se produise dans l'article. .. ..

Recommended Posts

[Entraînement compétitif] J'ai essayé AtCoder Beginner Contest 171
[Pratique professionnelle de compétition] J'ai essayé chez Coder Beginner Selection
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours Atcoder Débutant 153
Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Concours AtCoder Débutant 180 Remarque
Critique du concours AtCoder pour débutant 166
Concours AtCoder Débutant 182 Remarque
Critique du concours AtCoder
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Concours AtCoder pour débutants 167
Critique du concours AtCoder pour débutant 172
Concours AtCoder Débutant 183 Remarque
Critique du concours AtCoder
Concours AtCoder Débutant 184 Remarque
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
AtCoder Beginner Contest 181 Rapport de participation
AtCoder Beginner Contest 175 Inscription virtuelle
AtCoder Beginner Contest 161 Rapport de participation
AtCoder Débutant Contest 176 Rapport de participation
AtCoder Beginner Contest 154 Rapport de participation
Note de participation au concours pour débutants AtCoder # 003
AtCoder Beginner Contest 166 Rapport de participation
AtCoder Beginner Contest 153 Rapport de participation
AtCoder Beginner Contest 145 Rapport de participation
AtCoder Débutant Contest 184 Rapport de participation
Rapport de participation au concours AtCoder Débutant 160
AtCoder Beginner Contest 169 Rapport de participation
AtCoder Beginner Contest 178 Rapport de participation
AtCoder Beginner Contest 163 Rapport de participation
AtCoder Beginner Contest 159 Rapport de participation
AtCoder Beginner Contest 164 Rapport de participation
AtCoder Beginner Contest 168 Rapport de participation
Rapport de participation au concours AtCoder Débutant 150
AtCoder Beginner Contest 158 Rapport de participation
Rapport de participation au concours AtCoder Débutant 180
AtCoder Beginner Contest 162 Rapport de participation
AtCoder Débutant Contest 157 Rapport de participation
AtCoder Beginner Contest 167 Rapport de participation