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 )), et considérez quel sommet le rectangle contient (O ( n )). Le total est O ( n ^ 5 $), ce qui est juste à temps (en Python, c'est dans le temps, il faut donc réduire la quantité de calcul à O (n ^ 4) par la somme cumulative bidimensionnelle. Cette fois, je l'ai passé avec PyPy. ). Aussi, lors de la sélection des quatre côtés, il est inutile de compter les cas où les points contenus dans le rectangle sont inférieurs à k, donc pour éviter que de tels cas ne soient inclus, une rupture est faite lorsqu'elle tombe en dessous de k.

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 ) → O ( n ^ 4 \ times log (n) $) est également collé ci-dessous, mais comme la valeur de n est petite, elle ne peut pas être suffisamment accélérée. C'était (appel de fonction et tant que sont lents? Je pense que je peux le faire un peu mieux).

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)