AtCoder Beginner Contest 116 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-14 12.40.37.png

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

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes