[PYTHON] AtCoder Beginner Contest 075 Revue des questions précédentes
Temps requis
Impressions
Je n'ai pas pu résoudre le problème D car j'ai également fait d'autres courses pendant le bachacon cette fois-ci ... Il y a un concours aujourd'hui alors je ferai de mon mieux!
Problème A
Si b et c sont identiques, a est sorti, si c et a sont identiques, b est sorti, et si a et b sont identiques, c est sorti (cette fois, j'ai essayé de combiner deux opérateurs ternaires).
answerA.py
a,b,c=map(int,input().split())
print(a if b==c else b if c==a else c)
Problème B
8 Il suffit de juger du voisinage. Comment puis-je corriger la partie de jugement anormalement longue? J'ai reçu un commentaire et j'ai pu l'écrire brièvement. J'ai conçu ce qui suit. Puisque bool est une sous-classe de type entier, il peut être ajouté, et il peut être facilement jugé s'il est sur la carte en ajoutant un "." Autour de lui (** Je pense que cette simplification a également été faite dans le précédent problème d'AtCoder. J'ai utilisé. **).
answerB.py
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
def count_8(i,j):
global h,w,s
cnt=0
if i-1>=0 and j-1>=0:
if s[i-1][j-1]=="#":
cnt+=1
if i-1>=0 and j+1<=w-1:
if s[i-1][j+1]=="#":
cnt+=1
if i+1<=h-1 and j-1>=0:
if s[i+1][j-1]=="#":
cnt+=1
if i+1<=h-1 and j+1<=w-1:
if s[i+1][j+1]=="#":
cnt+=1
if i-1>=0:
if s[i-1][j]=="#":
cnt+=1
if j-1>=0:
if s[i][j-1]=="#":
cnt+=1
if i+1<=h-1:
if s[i+1][j]=="#":
cnt+=1
if j+1<=w-1:
if s[i][j+1]=="#":
cnt+=1
return str(cnt)
for i in range(h):
for j in range(w):
if s[i][j]=="#":
print("#",end="")
else:
print(count_8(i,j),end="")
print()
answerB_better.py
h,w=map(int,input().split())
s=[input()+"." if i!=h else "."*(w+1) for i in range(h+1)]
def count_8(i,j):
global h,w,s
cnt=(s[i-1][j-1]=="#")+(s[i-1][j+1]=="#")+(s[i+1][j-1]=="#")+(s[i+1][j+1]=="#") \
+(s[i-1][j]=="#")+(s[i][j-1]=="#")+(s[i+1][j]=="#")+(s[i][j+1]=="#")
return cnt
for i in range(h):
s_sub=""
for j in range(w):
if s[i][j]=="#":
s_sub+="#"
else:
s_sub+=str(count_8(i,j))
print(s_sub)
Problème C
Je l'ai fait avec une solution différente de la solution Writer. Premièrement, si vous considérez un sommet qui est connecté à un seul côté, ** le sommet sera non connecté ** si ce côté est exclu. Par conséquent, un tel côté est un pont car c'est un côté nécessaire pour être connecté. Ensuite, considérons le sommet (a) dans lequel deux côtés ou plus sont connectés. En supposant que l'un des deux côtés était un pont (a-b), ce pont serait un pont parce que b n'est pas déconnecté. Par conséquent, le ** pont pour le sommet a ** est l'autre pont. En d'autres termes, même dans le cas d'un côté ** n (> = 3), s'il y a n-1 ponts, l'autre côté sera également un pont **. Par conséquent, vous pouvez trouver tous les côtés qui sont des ponts en répétant le processus de vérification des sommets qui n'ont qu'un seul côté et en supprimant ces côtés, et en répétant jusqu'à ce qu'il n'y ait aucun sommet qui n'a qu'un seul côté.
answerC.py
n,m=map(int,input().split())
x=[[] for i in range(n)]
for i in range(m):
a,b=map(int,input().split())
x[a-1].append(b-1)
x[b-1].append(a-1)
def size0find():
global x,n
next=[]
for i in range(n):
if len(x[i])==1:
next.append(i)
k=x[i][0]
x[i].remove(k)
x[k].remove(i)
return next
cnt=0
while True:
y=size0find()
l=len(y)
if l==0:
break
cnt+=l
print(cnt)
Problème D
Il était difficile de faire une politique, alors je l'ai mise en œuvre tout en regardant la réponse. Je voudrais revoir tout en résumant les points sur lesquels se concentrer lors de la résolution du problème. Tout d'abord, j'ai noté tous les cas possibles, mais il est clair que je ne peux pas le faire à temps car le montant du calcul est de 10 $ ^ {15} $ ou plus (** je n'ai pas remarqué lors de la résolution ... **). C'était bien d'avoir fait une erreur dans la politique, mais j'ai senti que ** changer de là ** n'était toujours pas possible. Voici la solution TLE.
answerD_TLE.py
import itertools
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
t=[i for i in range(n)]
s=list(itertools.permutations(t,k))
#print(s)
l=len(s)
inf=10000000000
x_min=inf
y_min=inf
x_max=-inf
y_max=-inf
for i in range(n):
x,y=xy[i]
if x<x_min:x_min=x
if y<y_min:y_min=y
if x>x_max:x_max=x
if y>y_max:y_max=y
area=(x_max-x_min)*(y_max-y_min)
for i in range(l):
x_min=inf
y_min=inf
x_max=-inf
y_max=-inf
for j in range(k):
x,y=xy[s[i][j]]
if x<x_min:x_min=x
if y<y_min:y_min=y
if x>x_max:x_max=x
if y>y_max:y_max=y
#print(area)
area=min((x_max-x_min)*(y_max-y_min),area)
print(area)
Je vais écrire sur la bonne réponse d'ici.
Premièrement, ** l'aire du rectangle peut être trouvée une fois que les quatre côtés sont déterminés **. Il est également clair qu'il s'agit du plus petit rectangle lorsqu'il y a un point sur son côté. Par conséquent, ** rétrécissez chacun des quatre côtés pour qu'ils passent par les points, et trouvez le plus petit rectangle parmi les rectangles contenant K ou plus **.
Ici, la sélection des quatre côtés est $ _n C _2 $ (O ($ n ^ 4
answerD.py
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
i1_sub=n-i1
x_sub1=x[i1][0]
for l1 in range(i1_sub,1,-1):
x_sub2=x[i1+l1-1][0]
for i2 in range(n):
i2_sub=n-i2
y_sub1=y[i2][0]
for l2 in range(i2_sub,1,-1):
y_sub2=y[i2+l2-1][0]
z=[0]*n
for i in range(n):
if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
z[i]=1
if sum(z)>=k:
ans=min((x_sub2-x_sub1)*(y_sub2-y_sub1),ans)
else:
break
print(ans)
Post-scriptum (1/19)
Puisque mon hobby est d'augmenter la vitesse d'un facteur constant, j'accélérais également d'un facteur constant ce matin.
J'ai accéléré de 1357 ms à 619 ms dans la comparaison de vitesse par PyPy, mais cela ne passe toujours pas en Python (probablement cela ne passe pas à moins que ce soit 3 fois plus rapide).
De plus, le code corrigé de O ($ n ^ 5
answerD.py
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
ans=10**18*4
for i1 in range(n):
i1_sub=n-i1
x_sub1=x[i1][0]
for l1 in range(i1_sub,1,-1):
x_sub2=x[i1+l1-1][0]
for i2 in range(n):
i2_sub=n-i2
y_sub1=y[i2][0]
x_subsub=x_sub2-x_sub1
for l2 in range(i2_sub,1,-1):
y_sub2=y[i2+l2-1][0]
z=0
for i in range(n):
if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
z+=1
if z>=k:
ans=min(x_subsub*(y_sub2-y_sub1),ans)
break
else:
break
print(ans)
answerD.py
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for i in range(n)]
x,y=[[xy[i][0],i] for i in range(n)],[[xy[i][1],i] for i in range(n)]
x.sort()
y.sort()
inf=10**18*4
ans=inf
def upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
global n,k,xy
z=0
for i in range(n):
if x_sub1<=xy[i][0]<=x_sub2 and y_sub1<=xy[i][1]<=y_sub2:
z+=1
if z>=k:return True
return False
for i1 in range(n):
i1_sub=n-i1
x_sub1=x[i1][0]
for l1 in range(i1_sub,1,-1):
x_sub2=x[i1+l1-1][0]
x_subsub=x_sub2-x_sub1
for i2 in range(n):
ans_sub=inf
i2_sub=n-i2
y_sub1=y[i2][0]
l,r=2,i2_sub
if r<l:break
while l+1<r:
t=(l+r)//2
y_sub2=y[i2+t-1][0]
if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
r=t
else:
l=t
y_sub2=y[i2+r-1][0]
if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
ans=min(x_subsub*(y_sub2-y_sub1),ans)
if l!=r:
y_sub2=y[i2+l-1][0]
if upper_k(x_sub1,x_sub2,y_sub1,y_sub2):
ans=min(x_subsub*(y_sub2-y_sub1),ans)
print(ans)
Recommended Posts