[PYTHON] AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
Benötigte Zeit
Impressionen
Ich konnte das D-Problem nicht lösen, weil ich diesmal auch andere Besorgungen während des Bachacons gemacht habe ... Es gibt heute einen Wettbewerb, also werde ich mein Bestes geben!
Problem A
Wenn b und c gleich sind, wird a ausgegeben, wenn c und a gleich sind, wird b ausgegeben, und wenn a und b gleich sind, wird c ausgegeben (diesmal habe ich versucht, zwei ternäre Operatoren zu kombinieren).
answerA.py
a,b,c=map(int,input().split())
print(a if b==c else b if c==a else c)
B-Problem
8 Es reicht aus, die Umgebung zu beurteilen. Wie kann ich den ungewöhnlich langen Urteilsteil reparieren? Ich habe einen Kommentar erhalten und konnte ihn kurz schreiben. Ich habe folgendes entwickelt. Da bool eine Unterklasse vom Typ Integer ist, kann sie hinzugefügt werden, und es kann leicht beurteilt werden, ob sie sich auf der Platine befindet, indem ein "." Um sie herum hinzugefügt wird (** Ich glaube, dass diese Vereinfachung auch im vorherigen AtCoder-Problem vorgenommen wurde. Ich benutzte. **).
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)
C-Problem
Ich habe es mit einer anderen Lösung als der Writer-Lösung gemacht. Wenn Sie einen Scheitelpunkt betrachten, der nur mit einer Seite verbunden ist, ** ist der Scheitelpunkt nicht verbunden **, wenn diese Seite ausgeschlossen ist. Daher ist eine solche Seite eine Brücke, weil es eine notwendige Seite ist, die verbunden werden muss. Betrachten Sie als nächstes den Scheitelpunkt (a), in dem zwei oder mehr Seiten verbunden sind. Angenommen, eine der beiden Seiten wäre eine Brücke (a-b), wäre eine Brücke eine Brücke, da b nicht unverbunden ist. Daher ist die ** Brücke für den Scheitelpunkt a ** die andere Brücke. Mit anderen Worten, selbst im Fall der Seite ** n (> = 3), wenn es n-1 Brücken gibt, ist die andere Seite auch eine Brücke **. Daher ist es möglich, alle Seiten zu finden, die Brücken sind, indem die Arbeit des Überprüfens der Scheitelpunkte mit nur einer Seite und Entfernen dieser Seiten wiederholt und wiederholt wird, bis keine Scheitelpunkte mehr mit nur einer Seite vorhanden sind.
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)
D Problem
Es war schwierig, eine Richtlinie zu erstellen, daher habe ich sie implementiert, während ich mir die Antwort angesehen habe. Ich möchte die Punkte zusammenfassen, auf die ich mich bei der Lösung des Problems konzentrieren möchte. Zuerst habe ich alle möglichen Fälle aufgeschrieben, aber es ist klar, dass ich es nicht rechtzeitig schaffen kann, da der Rechenaufwand $ 10 ^ {15} $ oder mehr beträgt (** Ich habe es beim Lösen nicht bemerkt ... **). Es war gut, dass ich einen Fehler in der Richtlinie gemacht habe, aber ich hatte das Gefühl, dass ein Wechsel von dort immer noch nicht möglich war. Das Folgende ist die TLE-Lösung.
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)
Ich werde von hier aus über die richtige Antwort schreiben.
Erstens ** kann die Fläche des Rechtecks gefunden werden, sobald die vier Seiten bestimmt sind **. Es ist auch klar, dass es das kleinste Rechteck ist, wenn sich ein Punkt auf seiner Seite befindet. Verengen Sie daher ** jede der vier Seiten so, dass sie durch die Punkte verlaufen, und finden Sie das kleinste Rechteck unter den Rechtecken, die K oder mehr enthalten **.
Hier ist die Auswahl der vier Seiten $ _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)
Nachtrag (1/19)
Da mein Hobby darin besteht, die Geschwindigkeit um einen konstanten Faktor zu erhöhen, habe ich heute Morgen auch um einen konstanten Faktor beschleunigt.
Ich habe im Geschwindigkeitsvergleich von PyPy von 1357 ms auf 619 ms beschleunigt, aber es wird in Python immer noch nicht bestanden (wahrscheinlich nicht, es sei denn, es ist dreimal schneller).
Der aus 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