AtCoder Beginner Contest 075 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-18 8.17.24.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes