[PYTHON] AtCoder Beginner Contest 060 Review of past questions

D solved for the first time

Time required

Problem A

Compare front and back

answerA.py

a,b,c=input().split()
if a[-1]==b[0] and b[-1]==c[0]:
    print("YES")
else:
    print("NO")

answerA_better.py

a,b,c=input().split()
print("YES" if a[-1]==b[0] and b[-1]==c[0] else "NO")

B problem

I had a bug in my head and thought about it for about 10 minutes.

answerB.py

import fractions
a,b,c=map(int,input().split())
d=fractions.gcd(a,b)

if c%d==0:
    print("YES")
else:
    print("NO")

answerB_better.py

import fractions
a,b,c=map(int,input().split())
d=fractions.gcd(a,b)
print("YES" if c%d==0 else "NO")

C problem

I thought about it with my head buggy in B, so it seemed to be even more buggy. You can greedily count (?) Such problems from the front, but it is important to ** accurately grasp what happens after each person comes **, and the time at that time and the time to ask for an answer are Since they are different, prepare two variables. Cases should be classified according to whether or not hot water is available when a certain person arrives.

answerC.py

t=0
N,T=map(int,input().split())
nt=[int(i) for i in input().split()]
ans=0
for i in range(N):
    if nt[i]>t:
        ans+=T
    else:
        ans+=(T-(t-nt[i]))
    t=nt[i]+T
print(ans)

D problem

I had a short-circuited idea of simple knapsack → DP chance. I'm too crazy. If you look at the constraints, the maximum weight can be over $ 10 ^ 9 , so DP can't make it in time. If you look closely at the problem, you can see that ** n is extremely small ( O (n ^ 3) $ can afford it) and that it weighs only four ways **. In other words, there should be many items of the same weight, so you can see that ** it is better to select items of the same weight in descending order of value . Furthermore, even if you think about how many weights to choose from n <= 100 and turn the quadruple loop, it will only be about $ 25 ^ 4 <10 ^ 6 $, so you can afford it. ( This sense of computational complexity is important **) However, it is necessary to ** consider the cumulative sum first so that the sum of the things of each weight can be obtained by O (1) **. (C ++ seems to be in time without considering the cumulative sum.) A straightforward implementation of this is the code for answerD1.py. The code was unreadable, so I rewrote it to the code answerD2.py. (The quadruple loop is also a triple loop.) However, although it has been rewritten, there is still room for improvement, so answerD3.py is the one that used break a lot in the for loop in the latter half. I tried to make it the fastest code here and ended up with a code like answerD4.py (I devised a lot of the first sort part etc.), but only up to 32ms Kazu did not reach the fastest of 26ms. (It took me two hours to improve the code. It was hard.)

answerD1.py

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    if wv[i][0]==w0:
        k=wv[i][1]+x[0][-1]
        l=len(x[0])
        if l*w0<=w:x[0].append(k)
    elif wv[i][0]==w0+1:
        k=wv[i][1]+x[1][-1]
        l=len(x[1])
        if l*(w0+1)<=w:x[1].append(k)
    elif wv[i][0]==w0+2:
        k=wv[i][1]+x[2][-1]
        l=len(x[2])
        if l*(w0+2)<=w:x[2].append(k)
    else:
        k=wv[i][1]+x[3][-1]
        l=len(x[3])
        if l*(w0+3)<=w:x[3].append(k)
#print(x)
ma=0
for i in range(len(x[0])):
    for j in range(len(x[1])):
        for k in range(len(x[2])):
            for l in range(len(x[3])):
                ma_sub=0
                if i*w0+j*(w0+1)+k*(w0+2)+l*(w0+3)<=w:
                    ma_sub+=x[0][i]
                    ma_sub+=x[1][j]
                    ma_sub+=x[2][k]
                    ma_sub+=x[3][l]
                ma=max(ma,ma_sub)
print(ma)

answerD2.py

n,w=map(int,input().split())
wv=[list(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
for i in range(l3):
    for j in range(l2):
        for k in range(l1):
            d=w-(i*(w0+3)+j*(w0+2)+k*(w0+1))
            if d>=0:
                ma_sub=x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,len(x[0])-1)]
            ma=max(ma,ma_sub)
print(ma)

answerD3.py

n,w=map(int,input().split())
wv=[tuple(map(int,input().split())) for i in range(n)]
wv.sort(key=lambda x:-x[1])#reverse
wv.sort(key=lambda x:x[0])

w0=wv[0][0]
x=[[0],[0],[0],[0]]
for i in range(n):
    z=wv[i][0]-w0
    k=wv[i][1]+x[z][-1]
    l=len(x[z])
    if l*wv[i][0]<=w:
        x[z].append(k)
#print(x)
#print(w0)
ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)

answerD4.py

n,w=map(int,input().split())
w_sub,v_sub=map(int,input().split())
w0=w_sub
inf=1000000001
x=[[inf,v_sub],[inf],[inf],[inf]]
for i in range(n-1):
    w_sub,v_sub=map(int,input().split())
    z=w_sub-w0
    x[z].append(v_sub)
for i in range(4):
    x[i].sort(key=lambda x:-x)
    x[i][0]=0
    l_sub=len(x[i])
    for j in range(1,l_sub):
        x[i][j]+=x[i][j-1]

ma=0
l3=len(x[3])
l2=len(x[2])
l1=len(x[1])
l0=len(x[0])
for i in range(l3):
    for j in range(l2):
        d=w-i*(w0+3)-j*(w0+2)
        if d>=0:
            for k in range(l1):
                d=w-i*(w0+3)-j*(w0+2)-k*(w0+1)
                if d>=0:
                    ma=max(ma,x[3][i]+x[2][j]+x[1][k]+x[0][min(d//w0,l0-1)])
                else:
                    break
        else:
            break

print(ma)