[PYTHON] AtCoder Beginner Contest 076 Revue des questions précédentes
Temps requis
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.
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