[PYTHON] AtCoder Beginner Contest 119 Review of past questions
Time required
Impressions
Although it was a hassle to solve the C problem, I was able to solve it with a straightforward solution, so I felt the lack of concentration in the Bachacon. Also, I'm displaying the formula surrounded by $, but for some reason line breaks are inserted. I would be grateful if you could tell me how to deal with it. → Regarding this problem, it seems that a problem may occur when using the underscore (_). (2020/04/29)
Problem A
I didn't know if it was 2019 ..., misread ... If you use split, you can split with a backslash.
answerA.py
s=list(map(int,input().split("/")))
if s[0]<2019:
print("Heisei")
elif s[0]>2020:
print("TBD")
else:
print("TBD" if s[1]>4 else "Heisei")
answerA_better.py
s=list(map(int,input().split("/")))
print("TBD" if s[1]>4 else "Heisei")
B problem
All sums should be considered depending on whether they are bit coins or not.
answerB.py
n=int(input())
cnt=0.0
for i in range(n):
x,u=input().split()
x=float(x)
cnt+=(x if u=="JPY" else x*380000.0)
print(cnt)
C problem
It was more difficult than D (white eyes). ** It's clear that you can try all the streets **, but it was troublesome to write out all the streets, so when I was thinking about how to devise it, the time passed tremendously. When trying all the way, first note that ** MP depends only on how to choose bamboo and not in that order **. Based on this, you should think about ** A, B, C which bamboo to use for each bamboo ** (A, B, C, not used). Answer was implemented in this way.) First, number 0 to 2 (corresponding to A to C) for each of the original n bamboos to consider which bamboo to use, A, B, or C (1). At this point, the bamboo that can be used (or not required to be used) to make each of A, B, and C bamboo has been decided. Also, at this point, at least one number from 0 to 2 needs to appear, so if there is no number, the process moves to the next loop (2). Based on this, we will consider which bamboo to make each A, B, C, but ** Select any number of bamboos that can be used to make each A, B, C bamboo. Since it is good, consider a subset ** by bit string (3). However, even in this case, if you do not choose any bamboo, we will not consider it, so we will consider it excluding such cases (4). By thinking in this way, the MP required to determine the lengths of A, B, and C in each case can be uniquely determined (5), so by considering the minimum value for each, the subject is You can find the minimum MP. I implemented the above and it became as follows, but ** I was confused because I was too bad at naming variables ** and I was able to ** organize the above discussion in my head ** It took a long time to solve it. I think that I should write it out to keep my mind organized like every time, but when I solve it, I forget it. I thought that I had no choice but to imprint the attitude when solving it repeatedly.
answerC.py
import itertools
n,*abc=map(int,input().split())
l=[int(input()) for i in range(n)]
inf=100000000000000
mi=inf
for i in list(itertools.product([i for i in range(3)],repeat=n)):#(1)↓
sub=[[] for j in range(3)]
for j in range(n):
sub[i[j]].append(j)
mi_sub=0
for j in range(3):
l_sub=len(sub[j])
if l_sub==0:#(2)
mi_sub=inf
break
mi_subsub=inf
for k in range(2**l_sub):#(3)↓
mi_subsubsub=[0,0]
for l_subsub in range(l_sub):#(5)↓
if ((k>>l_subsub) &1):
mi_subsubsub[0]+=1
mi_subsubsub[1]+=l[sub[j][l_subsub]]
if mi_subsubsub[0]!=0:#(4)
mi_subsub=min(mi_subsub,abs(mi_subsubsub[1]-abc[j])+mi_subsubsub[0]*10-10)
mi_sub+=mi_subsub
mi=min(mi,mi_sub)
print(mi)
itertools.product A function that can generate a Cartesian product of multiple lists (you can write a multi-loop iterator concisely). By specifying multiple lists in the argument, an object of type itertools.product is generated and returned as a return value. Then, by turning the for statement, all the combinations can be retrieved one by one (it is also possible to list them). Furthermore, it is also possible to generate a direct product between the same list by specifying the number of repetitions in repeat, and in this problem, the direct product is generated with repeat = n for the list m.
D problem
At first, I thought that there was section scheduling and potato law, but I thought calmly and it wasn't. If you consider the problem based on the problem rather than the algorithm, you will not be addicted to the swamp and you will be able to think more. Now consider when you were at a certain x. Then x is surrounded by $ s_ {i-1} $, $ s_i $ and is surrounded by $ t_ {j-1} $, $ t_j $ ($ s_0 $, $ t_0 $). , $ s_ {a-1} $, $ t_ {b-1} $ is a little different if it is outside). At this time, the minimum movement is made by moving so as to pass through either the point of $ s_ {i-1} $ or $ s_i $ or the point of $ t_ {j-1} $ or $ t_j $. It's clear that the distance can be achieved (** draw a diagram and think about it before you notice this **), so you can check all four ways of $ 2 \ times2 $ (and $ s_0 $, $ t_0 $, If it is outside $ s_ {a-1} $, $ t_ {b-1} $, there are fewer candidate points to pass.). Furthermore, the range of x can be determined by the amount of log calculation by using a binary search, which makes the program sufficiently fast. These are implemented as follows: Also, the travel distance will be shorter if you visit from the closest of the two selected points.
answerD.py
a,b,q=map(int,input().split())
s=[int(input()) for i in range(a)]
t=[int(input()) for i in range(b)]
x=[int(input()) for i in range(q)]
from bisect import bisect_left
for i in range(q):
y=bisect_left(s,x[i])
z=bisect_left(t,x[i])
k=([0] if y==0 else [a-1] if y==a else [y-1,y])
l=([0] if z==0 else [b-1] if z==b else [z-1,z])
mi=100000000000000
for n in k:
for m in l:
if abs(s[n]-x[i])>abs(t[m]-x[i]):
sub1,sub2=t[m],s[n]
else:
sub1,sub2=s[n],t[m]
mi=min(mi,abs(sub1-x[i])+abs(sub2-sub1))
print(mi)
Correction (2020/05/03)
Fixed a link error.
Recommended Posts