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

Temps requis

スクリーンショット 2020-03-24 6.51.55.png

Impressions

J'étudie à l'étranger depuis trois semaines et j'ai été paresseux de jouer à des jeux sans jouer à la compétition. Je voudrais reprendre mon engagement. J'ai fait une erreur fondamentale dans le problème D et je me suis fané. J'ai pu voir que je ne me suis pas consacré récemment ...

Problème A

Notez que ce que vous voulez, ce sont les performances

answerA.py


r=int(input())
g=int(input())
print(g*2-r)

Problème B

Vous devriez l'évaluer avidement de l'avant.

answerB.py


n=int(input())
k=int(input())
x=1
for i in range(n):
    x=min(x+k,2*x)
print(x)

Problème C

Je voulais bien utiliser l'ordre du dictionnaire, mais je suis content de l'avoir fait sans être trop précis à ce sujet. Le numéro de la lettre S correspond à la toute première lettre de T|S|-|T|+Il existe un moyen, et nous vérifierons si un tel S existe réellement pour chacun d'eux. Aussi, je veux penser au plus petit dans l'ordre lexical.?Remplacez ceux non confirmés par un. Si vous essayez ceci dans l'ordre et que vous affichez finalement celui avec le plus petit ordre de dictionnaire parmi les candidats, vous pouvez afficher la réponse qui satisfait le sujet.

answerC.py


s=input()
l=len(s)
t=input()
k=len(t)
cand=[]
for i in range(l-k+1):
    new=""
    for j in range(l):
        if i<=j<i+k:
            if s[j]=="?":
                new+=t[j-i]
            else:
                if s[j]==t[j-i]:
                    new+=t[j-i]
                else:
                    break
        else:
            if s[j]=="?":
                new+="a"
            else:
                new+=s[j]
    if len(new)==l:
        cand.append(new)
cand.sort()
if len(cand)==0:
    print("UNRESTORABLE")
else:
    print(cand[0])

Problème D

C'est difficile à penser et c'est difficile à mettre en œuvre, mais cela ressemble à un problème bleu. Tout d'abord, dans ce problème ** si vous réglez correctement la vitesse, vous serez pris dans la limite de vitesse **, vous pouvez donc voir que vous devez décider de la vitesse dans l'ordre. De plus, lorsqu'il y a des sections avec des vitesses différentes, ** si vous décidez de la vitesse dans cette section dans l'ordre à partir de la section avec la vitesse la plus basse **, vous pouvez régler la vitesse dans toutes les sections tout en respectant la limite de vitesse de n'importe quelle section. (À l'inverse, si vous choisissez une section qui n'est pas la vitesse minimale, il y a des cas où la limite de vitesse n'est pas respectée.) Ici, considérez d'abord la vitesse dans la section ** ce qui arrivera aux première et dernière vitesses de la section **. Compte tenu du nombre de secondes pendant lesquelles la vitesse est éloignée de l'autre section où la vitesse est fixe, ** la vitesse maximale lors du passage de la section fixe à la section à laquelle vous pensez est Vous pouvez demander ** ce qui va se passer. Ce calcul est effectué pour chaque section où la vitesse est fixe, et ** la vitesse minimale est la réponse **. Il est également important de noter que pour les sections adjacentes, la dernière vitesse de la section précédente est égale à la première vitesse de la section suivante. En effectuant le calcul ci-dessus, nous avons pu déterminer quelles seraient les première et dernière vitesses de chaque section, mais ** nous devons augmenter la vitesse autant que possible dans cette section **. Quelle est la vitesse maximale dans cette section? Ensuite, avec la formule suivante? Peut être calculé, et par conséquent, combien de distance peut être parcourue jusqu'à cette section. La distance maximale peut être obtenue en ajoutant ceci pour toutes les sections.

IMG_0122.JPG

Le premier code est le code écrit en Bachacon, et le second code est le code qui a changé la partie qui se chevauchent du code.

answerD.py


import heapq
n=int(input())
inf=10000000000000
#Tenez le début et la fin
#Je l'ai fait fondre pendant une heure avec le même objet.
ans=[[-1,-1] for i in range(n)]
ans[-1][1]=0
ans[0][0]=0
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v2=[]
for i in range(n):
    heapq.heappush(v2,(v[i],i))
for i in range(n):
    #print(ans)
    y=heapq.heappop(v2)
    #print(y[1])
    #print(ans[y[1]])
    #print(y)
    #Décidez d'abord du début
    if ans[y[1]][0]==-1:
        #print(2)
        now1=0
        ansi1=inf
        for j in range(y[1]-1,-1,-1):
            #print(ans1)
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)
            now1+=t[j]
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
        now1=0
        for j in range(y[1],n):
            if ans[j][0]!=-1:
                ansi1=min(ansi1,ans[j][0]+now1)
            now1+=t[j]
            if ans[j][1]!=-1:
                ansi1=min(ansi1,ans[j][1]+now1)  
        ans[y[1]][0]=min(ansi1,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
        #print(ansi1)
    if ans[y[1]][1]==-1:
        #print(3)
        now2=0
        ansi2=inf
        for j in range(y[1],-1,-1):
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)
            now2+=t[j]
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
        now2=0
        for j in range(y[1]+1,n):
            if ans[j][0]!=-1:
                ansi2=min(ansi2,ans[j][0]+now2)
            now2+=t[j]
            if ans[j][1]!=-1:
                ansi2=min(ansi2,ans[j][1]+now2)  
        ans[y[1]][1]=min(ansi2,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]
        #print(ansi2)
answer=0
for i in range(n):
    h=min((t[i]+sum(ans[i]))/2,v[i])
    answer+=((h**2-ans[i][0]**2)/2)
    answer+=((h**2-ans[i][1]**2)/2)
    answer+=(h*(t[i]+sum(ans[i])-2*h))
print(answer)
#print(ans)

answerD_better.py


import heapq
n=int(input())
inf=10000000000000
ans=[[-1,-1] for i in range(n)]
ans[-1][1],ans[0][0]=0,0
t=list(map(int,input().split()))
v=list(map(int,input().split()))
v2=[]
for i in range(n):
    heapq.heappush(v2,(v[i],i))

def next(y,wh):
    global ans,n
    ansi=inf
    if wh:
        r1,r2=range(y[1]-1,-1,-1),range(y[1],n)
    else:
        r1,r2=range(y[1],-1,-1),range(y[1]+1,n)
    now=0
    for j in r1:
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)
        now+=t[j]
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
    now=0
    for j in r2:
        if ans[j][0]!=-1:
            ansi=min(ansi,ans[j][0]+now)
        now+=t[j]
        if ans[j][1]!=-1:
            ansi=min(ansi,ans[j][1]+now)  
    if wh:
        ans[y[1]][0]=min(ansi,y[0])
        ans[y[1]-1][1]=ans[y[1]][0]
    else:
        ans[y[1]][1]=min(ansi,y[0])
        ans[y[1]+1][0]=ans[y[1]][1]  

for i in range(n):
    y=heapq.heappop(v2)
    if ans[y[1]][0]==-1:next(y,True)
    if ans[y[1]][1]==-1:next(y,False)
answer=0
for i in range(n):
    h=min((t[i]+sum(ans[i]))/2,v[i])
    answer+=((h**2-ans[i][0]**2)/2)
    answer+=((h**2-ans[i][1]**2)/2)
    answer+=(h*(t[i]+sum(ans[i])-2*h))
print(answer)

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 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
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 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 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 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 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 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 104 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 090 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