AtCoder Beginner Contest 060 Revue des questions précédentes
D résolu pour la première fois
Temps requis
Problème A
Comparez l'avant et l'arrière
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")
Problème B
J'avais un bug dans la tête et j'y ai pensé pendant environ 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")
Problème C
J'y ai pensé avec mon buggy de tête en B, donc ça semblait être encore plus buggy. Vous pouvez compter avec avidité (?) De tels problèmes de l'avant, mais il est important de ** saisir avec précision ce qui se passe après que chaque personne est venue **, et le moment à ce moment-là et le moment de demander une réponse sont Puisqu'ils sont différents, préparez deux variables. Les cas peuvent être classés selon que l'eau chaude est disponible ou non lorsqu'une certaine personne arrive.
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)
Problème D
J'avais une idée à court terme d'un simple sac à dos → chance DP. Je suis trop fou.
Si vous regardez les contraintes, le poids maximum peut être supérieur à 10 $ ^ 9 answerD1.py.
Le code était illisible, donc je l'ai réécrit dans le code answerD2.py. (La boucle quadruple est également une triple boucle.)
Cependant, bien qu'il ait été réécrit, il y a encore place à l'amélioration, c'est donc `` answerD3.pyqui a utilisé beaucoup de pauses dans la seconde moitié de la boucle for. J'ai essayé d'en faire le code le plus rapide ici et je l'ai finalement fait quelque chose commeanswerD4.py``` (j'ai conçu une grande partie de la première partie de tri, etc.), mais ce n'est que jusqu'à 32 ms Kazu n'a pas atteint le plus rapide des 26 ms. (Il m'a fallu deux heures pour améliorer le code. C'était difficile.)
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)
Recommended Posts