[PYTHON] AtCoder Beginner Contest 062 Review of past questions

Past questions solved for the first time

Time required

Problem A

I thought it was annoying to classify cases depending on whether they were the same or not, but the answer was smarter.

answerA.py

x=[1,3,5,7,8,10,12]
y=[4,6,9,11]
z=[2]

a,b=map(int,input().split())

if (a in x and b in x) or (a in y and b in y) or (a in z and b in z):
    print("Yes")
else:
    print("No")

amswerA_better.py

xyz=[0,2,0,1,0,1,0,0,1,0,1,0]
a,b=map(int,input().split())
print("Yes" if xyz[a-1]==xyz[b-1] else "No")

B problem

Add "#" as appropriate

answerB.py

h,w=map(int,input().split())
hw=["#"*(w+2)]
for i in range(h):
    hw.append("#"+input()+"#")
hw.append("#"*(w+2))
for i in range(h+2):
    print(hw[i])

C problem

Although it was a C problem, it was difficult, but the difficulty was light blue. When I looked it up, it was the second slowest of the AC codes, but I personally like this muddy code. (I tried to write it, but it was a pretty terrible code. I regret it.) First, when it is divisible by 3, it outputs 0, but this is not necessary. In the else statement, there is a method to make a horizontally long rectangle with the first for statement and divide the remaining rectangle into two equal parts as much as possible, so there is a method to divide it vertically and horizontally. I have written out all the rectangular areas that seem to be felt. (I noticed while reviewing that ** there are a lot of overlaps and a lot of useless processing **.) The second is to make a vertically long rectangle and perform the same processing. Also, the second code is an improvement. The improvement process is like this. (I don't need the red part, so I erase it.) (The bottom is the first code.)

answerC.py

h,w=map(int,input().split())
if h%3==0 or w%3==0:
    print(0)
else:
    x=[]
    for i in range(1,w):
        sub=[]
        sub.append([h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)])
        sub.append([h*i,h*((w-i)//2+1),h*(w-i)-h*((w-i)//2+1)])
        sub.append([h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)])
        sub.append([h*i,(w-i)*(h//2+1),h*(w-i)-(w-i)*(h//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    for i in range(1,h):
        sub=[]
        sub.append([w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)])
        sub.append([w*i,w*((h-i)//2+1),w*(h-i)-w*((h-i)//2+1)])
        sub.append([w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)])
        sub.append([w*i,(h-i)*(w//2+1),w*(h-i)-(h-i)*(w//2+1)])
        for j in sub:
            x.append(max(j)-min(j))
    print(min(x))

answerC_better.py

h,w=map(int,input().split())
x=[]
for i in range(1,w):
    x1=[h*i,h*((w-i)//2),h*(w-i)-h*((w-i)//2)]
    x2=[h*i,(w-i)*(h//2),h*(w-i)-(w-i)*(h//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
for i in range(1,h):
    x1=[w*i,w*((h-i)//2),w*(h-i)-w*((h-i)//2)]
    x2=[w*i,(h-i)*(w//2),w*(h-i)-(h-i)*(w//2)]
    x.append(min(max(x1)-min(x1),max(x2)-min(x2)))
print(min(x))

D problem

The first half N elements of a'compose of the first 2N elements, and the second half N elements of a'compose of the last 2N elements. Here, when 2N elements are selected as a'and the N elements of the first half and the second half are considered, the last element of the first half is regarded as the k (N <= k <= 2N) th element of the original a. When you do, you can also see that the kth and earlier are included in the first half of a', and the kth and later are included in the latter half of a'. Furthermore, in order to maximize (sum of the first half N elements of a')-(sum of the second half N elements of a'), the sum of the first half N elements of a'is maximized. Since it is only necessary to minimize it, the first half k pieces are sorted in descending order and the sum of N elements is considered from the front, and the latter half 3N-k pieces are sorted in ascending order and the sum of N elements is considered from the front. is. However, if you simply move k and think about it, it becomes the amount of calculation of O (N * N * logN) and becomes TLE. So I thought about what would happen if I incremented k. We used a method of classifying whether the newly added element is smaller than the smallest element when incremented, and updating the sum if it is not added if it is small and if it is large, but this method is the smallest element. It was a hassle to save something and compare it one by one (the sum of the first half N elements of a'is considered here). What I should have come up with here is the use of ** Priority_queue **. When you think about it later, there are many obvious points. This is because Priority_queue ** can retrieve high priority elements in logarithmic hours and push speed in logarithmic hours **. Why didn't you decide to use Priority_queue when trying to ** separate cases with the smallest (or maximum) as the boundary **? regretting. Once I made a policy, I was able to do one pan, Priority_queue is great. I haven't used Python's heapq much because I often use C ++'s Priority _ queue, but I wonder if I can change the priority like C ++ isn't it inconvenient? I'll try to find out what I can do if I feel like it (I don't want to do it because it's a hassle if I have to make a new one in the class).

answerD.py

import heapq

n=int(input())
a1=[]
b1=[]
a2=[]
b2=[]
s=input().split()
for i in range(3*n):
    if i<n:
        a1.append(int(s[i]))
    elif i>=2*n:
        b1.append(-int(s[i]))
    else:
        a2.append(int(s[i]))
        b2.append(-int(s[3*n-i-1]))
suma=[sum(a1)]
sumb=[sum(b1)]
heapq.heapify(a1)
heapq.heapify(b1)

for i in range(0,n):
    heapq.heappush(a1,a2[i])
    k=heapq.heappop(a1)
    l=suma[-1]
    suma.append(l+a2[i]-k)
for i in range(0,n):
    heapq.heappush(b1,b2[i])
    k=heapq.heappop(b1)
    l=sumb[-1]
    sumb.append(l+b2[i]-k)

ma=-1000000000000000
for i in range(n+1):
    ma=max(ma,suma[i]+sumb[-i-1])
print(ma)