Time required

Impressions

This time I was stuck with the C problem and couldn't even challenge the problems after that ... I thought it was important to clarify the policy ** because if I was impatient, I would repeat appropriate experiments. Next time I have a problem with a pattern that I have never solved, I would like to consider it firmly so as not to forget the above.

Problem A

It is not difficult if you pay attention to the difference between H and M.

`answerA.py`


h1,m1,h2,m2,k=map(int,input().split())
print((h2-h1)*60+(m2-m1)-k)

Problem B

I doubted DP for a moment, but in the end it is good to think about how much the "Doctor / PD index" will increase depending on whether you change? To P or D **. When changing to P, it increases by 1 only when the character immediately after it is D, but when changing to D, it increases by 1 by changing the character itself, and when the character immediately before it is P, it increases by 1 so all? You can see that it is best to change it to D.

`answerB.py`


t=input()
t=t.replace("?","D")
print(t)

C problem

When I was thinking about it, I found it difficult, but when I looked at the answer, it was a natural answer, so I thought it was necessary to calm down and ** have some time to set the policy.

First and foremost, the policy is to ** record the number of vertices at each depth **. If you do not set this, you will not even be able to set it on the starting line, but I think that it is not difficult because the condition of the number of leaves is given for each depth due to the problem.

Under this, ** determine the number of vertices in order from the place closest to the root **, and because it is a binary tree, the maximum number of vertices at each depth $ d $ is ** depth $ d-1 $ You can see that it is twice the number of vertices minus the number of leaves in. However, you can see in the second sample that if you increase it in this way, you will end up with a pattern of ** eventually becoming too many and leaving more leaves **. … ①

Therefore, I tried to adjust it so that it was not too much, but I couldn't solve it because ** I did it properly without trying to verbalize this adjustment **.

Also, during the discussion, I was able to formulate a policy to decide from the opposite, but I could not find out. As you can see from the second sample (shown below), ** the number of vertices at depth $ d $ must be less than or equal to the sum of the leaves below $ d $ depth **. As shown in the figure below, for vertices that are not leaves at a depth of $ d $, if you follow vertices with a depth of $ d + 1 $ or more, leaves will always exist at some depth and different paths will not point to the same vertex. It can be said as above. … ②

If you can consider (1) and (2), increase the number of vertices as much as possible according to (1) within the upper limit of (2) in order from the closest to the root, based on the cumulative sum of the array that preserves the number of vertices with a depth of d or less. It's fine.

Also, regarding the consideration of (2), I think that it is not difficult because ** I can think about what the upper limit is if I want to increase it as much as possible but I cannot increase it **. (After all, it is important to consider while organizing **, but if you are accustomed to ABC, there are many problems that are easy to consider, so I forget it ...)

I was frustrated that I couldn't solve it during the contest, but I felt that it was a good question that I could consider in order if I calmed down.

`answerC.py`


from itertools import accumulate
n=int(input())
a=list(map(int,input().split()))
c=list(accumulate(a))
b=[0]*(n+1)
def f():
    global n,a,b
    for i in range(n+1):
        if i==0:
            b[0]=min(c[n]-c[0],1)
        else:
            b[i]=min(2*(b[i-1]-a[i-1]),c[n]-c[i-1])

    if n==0:
        if a[0]!=1:
            print(-1)
        else:
            print(1)
    elif b[n]!=a[n]:
        print(-1)
    else:
        print(sum(b))
f()

`answerC_shortest.py`


p=print;n,*a=map(int,open(0).read().split());t=sum(a);p(sum([w:=1]+[exit(p(-1))if(w:=min(2*(w-q),t:=t-q))<0 else w for q in a]))

After D problem

Since it is ARC and lacks ability, it is judged that the priority is low and will not be explained in this article.

NOMURA Programming Contest 2020 Review