Temps requis

Impressions

Cette fois, j'étais coincé avec le problème C et je ne pouvais même pas contester les problèmes après cela ... J'ai pensé qu'il était important de clarifier la politique ** car si j'étais impatient, je répéterais les expériences appropriées. Ensuite, quand j'ai un problème avec un motif que je n'ai jamais résolu, j'aimerais le considérer fermement pour ne pas oublier ce qui précède.

Problème A

Ce n'est pas difficile si vous faites attention à la différence entre H et M.

`answerA.py`


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

Problème B

J'ai douté de DP pendant un moment, mais au final, il est bon de penser à combien va augmenter l '«indice Docteur / PD» selon que l'on passe à P ou D **. Lors du passage à P, il augmente de 1 uniquement lorsque le caractère immédiatement après est D, mais lors du passage à D, il augmente de 1 en changeant le caractère lui-même, et lorsque le caractère immédiatement avant est P, il augmente de 1 donc tout? Vous pouvez voir qu'il est préférable de le changer en D.

`answerB.py`


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

Problème C

Quand j'y réfléchissais, je trouvais cela difficile, mais quand j'ai regardé la réponse, c'était une réponse naturelle, alors j'ai pensé qu'il était nécessaire de se calmer et ** avoir un peu de temps pour définir la politique.

Tout d'abord, la politique consiste à ** enregistrer le nombre de sommets à chaque profondeur **. Si vous ne configurez pas cela, vous ne pourrez même pas vous tenir sur la ligne de départ, mais je ne pense pas que ce soit difficile car le problème est que le nombre de feuilles est défini pour chaque profondeur.

Sur cette base, ** déterminez le nombre de sommets dans l'ordre à partir du plus proche de la racine **, et comme il s'agit d'un arbre dichotomisé, le nombre maximum de sommets à chaque profondeur $ d $ est ** profondeur $ d-1 $ Vous pouvez voir que c'est deux fois le nombre de sommets moins le nombre de feuilles. Cependant, vous pouvez voir dans le deuxième échantillon que si vous l'augmentez de cette manière, vous vous retrouverez avec un modèle qui ** finit par devenir trop nombreux et les feuilles restent **. … ①

Par conséquent, j'ai essayé de l'ajuster pour que ce ne soit pas trop, mais je n'ai pas pu le résoudre parce que ** je l'ai fait correctement sans essayer de verbaliser cet ajustement **.

Aussi, au cours de la discussion, j'ai pu formuler une politique pour décider du contraire, mais je n'ai pas pu le savoir. Comme vous pouvez le voir dans le deuxième exemple (ci-dessous), ** le nombre de sommets à la profondeur $ d $ doit être inférieur ou égal à la somme des feuilles en dessous de $ d $ profondeur **. Comme le montre la figure ci-dessous, pour un sommet qui n'est pas une feuille à une profondeur de $ d $, si vous suivez un sommet avec une profondeur de $ d + 1 $ ou plus, il y aura toujours une feuille à une certaine profondeur et des chemins différents ne pointeront pas vers le même sommet. On peut dire comme ci-dessus. … ②

Si vous pouvez considérer ① et ②, augmentez le nombre de sommets autant que possible en fonction de ① dans la limite supérieure de ② dans l'ordre du plus proche de la racine, en fonction de la somme cumulée du tableau qui préserve le nombre de sommets avec une profondeur de d ou moins. C'est bon.

De plus, en ce qui concerne la prise en compte de (2), je pense que ce n'est pas difficile parce que ** je veux l'augmenter autant que possible, mais si j'ai le sentiment que je ne peux pas l'augmenter, je ne peux considérer que la limite supérieure **. (Après tout, c'est important à considérer lors de l'organisation **, mais si vous êtes habitué à ABC, il y a beaucoup de problèmes faciles à considérer, alors je l'oublie ...)

J'étais frustré de ne pas pouvoir le résoudre pendant le concours, mais j'ai senti que c'était une bonne question que je pourrais considérer dans l'ordre si je me calmais.

`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]))

Problème après D

Comme il s'agit d'un ARC et qu'il manque de capacité, il est jugé que la priorité est faible et ne sera pas expliquée dans cet article.

[PYTHON] Revue du concours de programmation NOMURA 2020