[PYTHON] AtCoder Beginner Contest 116 Revue des questions précédentes
Temps requis
Impressions
Je n'ai pas pu obtenir le WA pour le problème D, donc j'ai dû passer environ deux heures après le concours pour obtenir le WA. De plus, l'idée était correcte et une seule ligne était fausse. C'était douloureux. De plus, c'était une erreur stupide, alors j'aimerais y réfléchir et m'en servir la prochaine fois.
Problème A
Divisez le produit des côtés qui prennent l'angle droit par 2.
answerA.py
a,b,_=map(int,input().split())
print(a*b//2)
Problème B
En d'autres termes, vous pouvez sortir l'index lorsqu'il sort pour la deuxième fois, donc gérez les nombres avec set et sortez l'index lorsque les nombres déjà en set sortent et se cassent. C'est bon.
answerB.py
x=set()
s=int(input())
ans=0
while True:
ans+=1
if s in x:
print(ans)
break
x.add(s)
if s%2==0:
s=s//2
else:
s=3*s+1
Problème C
Personnellement, c'était vraiment difficile. Au lieu d'arroser pour élever la hauteur des fleurs, j'ai pensé à l'abaisser à partir de la hauteur finale des fleurs pour rendre toutes les hauteurs des fleurs 0. De plus, à ce moment, le nombre minimum est sélectionné pour la pièce où les nombres autres que ** sont continus, et le numéro de la pièce sélectionnée est réduit de ce nombre **. Il est nécessaire de récupérer l'index de l'extrémité gauche et de l'extrémité droite de la pièce ((1) et (2) lui correspondent). De plus, comme l'opération de sélection du nombre minimum en (2) est effectuée en même temps, la hauteur est réduite du nombre minimum en (3). Vous pouvez résoudre le problème en additionnant combien vous avez abaissé la hauteur de toutes les fleurs jusqu'à ce que vous ayez réduit la hauteur de toutes les fleurs à 0.
answerC.py
n=int(input())
h=list(map(int,input().split()))
ans=0
while True:
l,m=-1,-1
#(1)
for i in range(n):
if h[i]!=0:
l=i
break
if l==-1:
break
if l==n-1:
ans+=h[l]
break
r=l
#(2)
for i in range(l,n):
if h[i]==0:
break
else:
r=i
if m==-1:
m=h[i]
else:
m=min(m,h[i])
#(3)
for i in range(l,r+1):
h[i]-=m
ans+=m
print(ans)
Problème D
Au début, j'ai essayé de fixer le type de matériel **, mais je ne pensais pas qu'il y avait un moyen efficace de déterminer le type, alors je l'ai immédiatement rejeté. Ici, si vous voulez manger le même type de matière, j'ai pensé qu'il valait mieux choisir celle avec les points de goût de base les plus élevés, alors commencez par ** organiser par ordre décroissant des points de délices de base et sélectionner le matériau Kth ** J'ai pensé. Ici, afin d'augmenter les points de satisfaction tout en sélectionnant le matériau avec un point de base de délice inférieur au matériau K, ** il est nécessaire d'augmenter les types et d'augmenter les points bonus de type **. De plus, le matériau qui améliore le bonus de type sera ** celui avec les points de base les plus élevés de délicieux parmi les types de matériaux qui n'ont jamais été vus auparavant **. De plus, pour le matériau qui est exclu lors de la sélection d'un matériau qui améliore le bonus de type, ** les points de bonus de type ne doivent pas être réduits **, donc ** les points de base les plus délicieux du type de matériau qui a deux ou plusieurs types de matériaux Est faible **. De plus, comme il est nécessaire d'enregistrer le nombre de types de documents qui ont été pris jusqu'à présent, ils sont enregistrés dans un dictionnaire appelé kl. Par conséquent, il serait bon de les implémenter docilement, mais la mise en œuvre était un peu gênante. Par conséquent, ** j'ai oublié de définir la variable now sur -1 pour numériser le matériau suivant après avoir retiré le matériau **, et la vérification a pris environ deux heures. De plus, j'ai fait cette vérification après le bachacon, mais c'était lent car ** maintenant n'était pas sauvegardé et tous les index de 0 à k-1 étaient scannés à chaque fois ** pendant le bachacon. Je veux m'assurer d'améliorer le programme dès que je sens que le montant du calcul est suspect. De plus, je pensais que le code serait difficile à lire lorsque d'autres personnes le liraient, j'ai donc laissé beaucoup de notes dans le commentaire. Veuillez également vous référer au commentaire hors du code.
answerD.py
n,k=map(int,input().split())
#td est organisé par ordre de taille
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])
#Ce qui suit est un code pour trouver le point de satisfaction lors de la sélection de celui avec le point de base le plus élevé de délicieux jusqu'au kth
ans=0
kl=dict()
for i in range(k):
ans+=td[i][1]
if td[i][0] in kl:
kl[td[i][0]]+=1
else:
kl[td[i][0]]=1
l=len(kl)
ans+=(l**2)
ans_=ans
#Ci-dessous le code pour choisir le matériel pour augmenter le type de points bonus
now=k-1 #Le matériau qui peut être exclu est 0~Recherche par index jusqu'à maintenant
for i in range(k,n): #Kind Le matériau qui augmente les points bonus est k~n-Recherche dans l'ordre par index jusqu'à 1
if td[i][0] not in kl: #Dans le cas d'un matériau qui n'a pas encore été sélectionné
while now>=0: #Y a-t-il du matériel qui peut être enlevé?(now<S'il vaut 0, la numérisation est terminée, donc elle se termine.)
if kl[td[now][0]]>1: #Seuls les types de matériaux qui ont plus d'un matériau peuvent être exclus
mi=td[now] #Notez les types de matières à exclure et les points de base de la gourmandise
kl[mi[0]]-=1 #Réduisez le nombre de ce type de matériau par un
now-=1 #Numériser à partir du prochain matériau supprimé
break
now-=1 #S'il n'y a qu'un seul matériau, numérisez le suivant
if now==-1: #Si vous avez terminé la numérisation
break
else:
ans=ans+2*l+1-mi[1]+td[i][1] #Notez les points de satisfaction lors de l'augmentation du type de points bonus(mise à jour)
kl[td[i][0]]=1 #Enregistrer le type de matériau
ans_=max(ans,ans_)#Mettre à jour si les points de satisfaction sont dépassés
l+=1 #Augmentez de un le type de matériau(J'ai pensé qu'il était trop tard pour l'obtenir avec len)
print(ans_)
Recommended Posts