Revue du concours de programmation NOMURA 2020

Temps requis

スクリーンショット 2020-06-02 12.16.41.png

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. … ②

IMG_0395.PNG

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.

Recommended Posts

Revue du concours de programmation NOMURA 2020
Examen du concours de programmation Keyence 2020
Examen du concours de programmation HHKB 2020
concours yukicoder 259 avis
concours yukicoder 264 avis
Concours de programmation Acing 2020
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Bilan 2019 du concours de programmation Sumitomo Mitsui Trust Bank
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Grand Contest 048 Critique
Critique du concours AtCoder Débutant 181
Après le "Concours de programmation Diverta 2019"
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 044 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
Critique du concours AtCoder
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Revue du concours régulier AtCoder 104
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours de programmation Atcoder Acing Python
Notes pour le concours de programmation HHKB 2020
atcoder Review of Panasonic Programming Contest 2020, jusqu'à la question E (Python)
Rapport de participation au concours de programmation AtCoder HHKB 2020
Rapport de participation au concours de programmation AtCoder Acing 2020
AtCoder Beginner Contest 066 Revoir les questions précédentes
Rapport de participation au concours de programmation AtCoder Keyence 2020
Rapport de participation au concours de programmation AtCoder Panasonic 2020
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 062 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