[PYTHON] AtCoder Beginner Contest 076 Review of past questions
Time required
Impressions
I've been studying abroad for the last three weeks and have been lazy about playing games without playing a professional competition. I would like to resume my devotion. I made a basic mistake in the D problem and withered. I could see that I haven't been devoting myself recently ...
Problem A
Note that what you want is performance
answerA.py
r=int(input())
g=int(input())
print(g*2-r)
B problem
You should greedily evaluate it from the front.
answerB.py
n=int(input())
k=int(input())
x=1
for i in range(n):
x=min(x+k,2*x)
print(x)
C problem
I wanted to use the dictionary order well, but I'm glad I did it without being too particular about it. Which letter of S corresponds to the very first letter of T|S|-|T|+There is one way, and we will check if such S actually exists for each of them. Also, I want to think of the smallest one in dictionary order.?Replace unconfirmed ones with a. If you try this in order and finally output the one with the smallest dictionary order among the candidates, you can output the answer that satisfies the subject.
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])
D problem
It's hard to think about and it's hard to implement, but it feels like a blue problem. First of all, in this problem ** if you set the speed properly, you will get stuck in the speed limit **, so you can see that you need to decide the speed in order. Also, when there are sections with different speeds, ** if you decide the speed within that section in order from the section with the lowest speed **, you can set the speed in all sections while observing the speed limit of any section. (On the contrary, if you decide from the section that is not the minimum speed, there are cases where the speed limit is not met). Here, first consider the speed within the section ** what will happen to the first and last speed of the section **. Considering how many seconds the speed is away from the other section where the speed is fixed, ** the maximum speed when moving from the fixed section to the section you are thinking about is You can ask for ** what happens. This calculation is performed for the section where each speed is fixed, and ** the minimum speed is the answer **. It is also important to note that for adjacent sections, the last speed of the previous section is equal to the first speed of the next section. By performing the above calculations, we were able to find out what the speeds at the beginning and end of each section would be, but ** we need to increase the speed as much as possible within that section **. What is the maximum speed in that section? Then, with the following formula? And, as a result, how much distance can be traveled up to that section. The maximum distance can be obtained by adding this for all sections.
The first code is the code written in the bachacon, and the second code is the code that changed the overlapping part of the code.
answerD.py
import heapq
n=int(input())
inf=10000000000000
#Hold the beginning and end
#I melted it for an hour with the same object.
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)
#Decide the beginning first
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