AtCoder Beginner Contest 075 Review of past questions

Time required

Impressions

I did other errands during the virtual console this time as well, and I couldn't solve the D problem ... There is a contest today so I'll do my best!

Problem A

Output a if b and c are the same, b if c and a are the same, and output c if a and b are the same (this time I tried combining two ternary operators).

answerA.py

a,b,c=map(int,input().split())
print(a if b==c else b if c==a else c)

B problem

8 It suffices to judge the neighborhood. How can I fix the abnormally long judgment part? I received a comment and was able to write it short. I devised the following. Since bool is an integer type subclass, it can be added, and it can be easily judged whether it is on the board by adding "." Around it (** I feel that this simplification was also done in the previous AtCoder problem. I used. **).

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

I did it with a different solution from the Writer solution. First, if you consider a vertex that has only one side connected, ** the vertices will be unconnected ** if that side is excluded. Therefore, such edges are bridges because they are necessary edges to be connected. Next, consider the vertex (a) that is connected by two or more sides. Assuming that one of the two sides was a bridge (a-b), that one bridge would be a bridge because b is not unconnected. Therefore, the ** bridge for vertex a ** is the other bridge. In other words, even in the case of ** n (> = 3) side, if there are n-1 bridges, the other side will also be a bridge **. Therefore, you can find all the sides that are bridges by repeating the work of checking the vertices that have only one side and removing those sides, and repeating until there are no vertices that have only one side.

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

It was difficult to make a policy, so I implemented it while looking at the answer. I would like to review while summarizing the points to focus on when solving the problem. First of all, I wrote down all possible cases, but it is clear that I can not make it in time because the amount of calculation is $ 10 ^ {15} $ or more (** I did not notice when solving ... **). It was good that I made a mistake in the policy, but I felt that ** switching from there ** was still not possible. The following is the TLE solution.

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)

I will write about the correct answer from here.

First, ** the area of the rectangle can be found once the four sides are determined **. It is also clear that it is the smallest rectangle when there is a point on its side. Therefore, ** narrow down each of the four sides so that they pass through the points, and find the smallest rectangle among the rectangles containing K or more **. Here, the method of selecting the four sides is $ _n C _2 $ (O ($ n ^ 4 )), and consider which vertex the rectangle contains (O ( n )). The total is O ( n ^ 5 $), which is just in time (in Python, it is in time, so it is necessary to reduce the amount of calculation to O (n ^ 4) by the two-dimensional cumulative sum. This time, I passed it with PyPy. ). Also, when selecting four sides, it is useless to count the cases where the points contained in the rectangle are smaller than k, so to prevent such cases from being included, break is made when it falls below 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)

Postscript (1/19)

My hobby is constant times faster, so I was doing constant times faster this morning as well. I speeded up from 1357ms to 619ms in the speed comparison by PyPy, but it still doesn't pass in Python (probably it doesn't pass unless it is 3 times faster). Also, the code corrected from O ($ n ^ 5 ) → O ( n ^ 4 \ times log (n) $) is also pasted below, but since the value of n is small, it cannot be speeded up sufficiently. It was (function call and while are slow? I think I can do it a little better).

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)