[PYTHON] AtCoder Beginner Contest 116 Review of past questions

Time required

Impressions

I couldn't get the WA for the D problem, so I had to spend about two hours after the contest to get the WA. What's more, the idea was correct and only one line was wrong. It was painful. Moreover, it was a silly mistake, so I would like to reflect on it and make use of it next time.

Problem A

Divide the product of the sides that sandwich the right angle by 2.

answerA.py

a,b,_=map(int,input().split())
print(a*b//2)

B problem

In other words, you can output the index when it comes out for the second time, so manage the numbers with set and output the index when the numbers already in set come out and break. It's fine.

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

C problem

Personally, it was really difficult. Instead of watering to raise the height of the flowers, I thought of lowering it from the final height of the flowers to make all the heights of the flowers 0. Also, at this time, the minimum number is selected for the part where the numbers other than ** are continuous and the number of the selected part is reduced by that number ** The operation is repeated, so the numbers other than 0 are continuous. It is necessary to fetch the index of the left end and the right end of the part ((1) and (2) correspond to it). Also, since the operation of selecting the minimum number in (2) is performed at the same time, the height is reduced by the minimum number in (3). You can solve the problem by doing the above and summing up how much you lowered the height of all the flowers before making them 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)

D problem

At first, I tried to fix the type of material **, but I didn't think there was an effective way to determine the type, so I immediately rejected it. Here, if you want to eat the same kind of material, I thought that it would be better to choose the one with the highest basic taste points, so first ** arrange in descending order of the basic deliciousness points and select the Kth material ** I thought. Here, in order to increase the satisfaction points while selecting the material with a lower basic point of deliciousness than the K material, ** it is necessary to increase the types and increase the type bonus points **. In addition, the material that enhances the type bonus will be ** the one with the highest basic points of deliciousness among the types of material that have never been seen before **. Furthermore, for the material that is excluded when selecting one material that enhances the type bonus, ** the type bonus point must not be lowered **, so ** the most delicious basic point of the type that has two or more types of material Is low **. Also, since it is necessary to record how many types of material have been taken so far, it is saved in a dictionary called kl. Therefore, it would be good to implement these obediently, but the implementation was a little troublesome. Therefore, ** I forgot to set the now variable to -1 to scan the next material after removing the material **, and it took about two hours to check. Also, I did that check after the virtual console, but it was slow because ** now was not saved and all indexes from 0 to k-1 were scanned every time ** during the virtual console. I want to make sure to improve the program as soon as I feel that the amount of calculation is suspicious. Also, I thought the code would be difficult to read when other people read it, so I left a lot of notes in the comment out. Please also refer to the comment out of the code.

answerD.py

n,k=map(int,input().split())
#td is arranged in order of size
td=sorted([list(map(int,input().split())) for i in range(n)],reverse=True,key=lambda x:x[1])

#The following is a code to find the satisfaction point when choosing the kth one with the highest basic deliciousness point.
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

#Below is the code for choosing the material to increase the type bonus points
now=k-1 #The material that can be excluded is 0~Search by index up to now
for i in range(k,n): #Kind The material that increases bonus points is k~n-Search in order by index up to 1
    if td[i][0] not in kl: #In the case of material that has not been selected so far
        while now>=0: #Is there any material that can be removed?(now<If it is 0, scanning is finished, so it ends.)
            if kl[td[now][0]]>1: #Only types of material that have more than one material can be excluded
                mi=td[now] #Make a note of the types of material to be excluded and the basic points of deliciousness
                kl[mi[0]]-=1 #Reduce the number of that type of material by one
                now-=1 #Scan from the next material removed
                break
            now-=1 #If there is only one material, scan the next
        if now==-1: #If you have finished scanning
            break
        else:
            ans=ans+2*l+1-mi[1]+td[i][1] #Make a note of the satisfaction points when you increase the type bonus points(update)
            kl[td[i][0]]=1 #Record the type of material
            ans_=max(ans,ans_)#Update if satisfaction points are exceeded
            l+=1 #Increase the type of material by one(I thought it was too late to get it with len)
print(ans_)