[PYTHON] AtCoder Beginner Contest 117 Review of past questions

Time required

Impressions

From this time, I started to use the virtual console function of AtCoder Problems! (Because Estimated Perfomance comes out) When I solved it once before, I couldn't compete with the D problem at all and didn't review it, but I solved the similar problem smoothly because I solved it before. For the D problem, it is good to be aware of the digit DP, but I feel that I have learned a lot.

Problem A

You can multiply it by 1 / t.

answerA.py

t,x=map(int,input().split())
print(t/x)

B problem

Compare the sum of the longest side and the other sides.

answerB.py

n=int(input())
l=sorted(list(map(int,input().split())))
print("Yes" if l[-1]<sum(l[:-1]) else "No")

C problem

When n> = m, you can place pieces at all points without moving, so it will be 0. When n <m, select the cell where each frame can be placed, but when experimenting, it is assumed that between $ X_i $ and $ X_ {i + 1} $ ($ X_i $ is sorted in ascending order). When $ Y_i $ is set to.), You can visit all the squares by selecting mn different $ Y_i $ (conversely, even if you select less than this number of $ Y_i $, all the cells. You cannot visit the trout.) Therefore, select the smallest m-n of $ Y_i $ and output the total. This problem is a common pattern and should be mastered. (It is important that ** it is a section that you pass by moving ** and that ** you can freely choose the section **.)

answerC.py

n,m=map(int,input().split())
x=sorted(list(map(int,input().split())))
y=sorted([x[i+1]-x[i] for i in range(m-1)])
if n>=m:
    print(0)
else:
    print(sum(y[:m-n]))

D problem

I think that it is a problem with a high learning effect because it is necessary to know the characteristics of XOR while including the idea of digit DP of the pattern of ** K or less, which is very frequent. The basic idea of digit DP etc. can be easily understood by looking at Kenchon's article. Below, I will explain including my own points of view.

First, pay attention to each digit that is the basis of XOR (it is a digit in binary. Please note that the digit in the following is a digit in binary). At this time, consider ** maximizing each digit **, but the i-th digit of $ X \ XOR \ A_k $ (k = 1 ~ N) is 0 or 1, and the i of $ A_k $ When the digit is 0, the i-th digit of X is 1 and when the i-th digit of $ A_k $ is 0, the i-th digit of X can be set to 1 to maximize the digit (1). I will. Therefore, count whether the i-th digit of $ A_1 $ ~ $ A_N $ is 0 or 1, and if there are many ** 0, set the i-th digit of X to 1 and if there are many 1, set the i-th digit of X to 0. ** is the case where the sum of $ X \ XOR \ A_1 $ ~ $ X \ XOR \ A_N $ in the i-th digit is maximized. However, there is also a condition of 0 or more and K or less here, so we will consider this condition from here. Considering the case where it is less than or equal to K, ** when counting from the upper digit, the i-th digit is equal to K, and the i + 1-th digit is smaller than K ** (this). That is the idea of the digit DP of the pattern below K!). Also note that each digit is 0 or 1 here.

First of all, since both 0 and 1 can be taken after the i + 1 digit, check whether both 0 and 1 can be taken with the check variable (initialize with False at first). Furthermore, let X (X = 1 ~ K) be the number that maximizes f. Here, if the jth digit is 1 when looking at K from the upper digit, X can take both 0 and 1. Furthermore, if the jth digit of X takes 0, then the jth digit of X is smaller than K, so the subsequent digits can take 0 or 1 freely (set check to True). ). On the contrary, if the jth digit of K is 0, taking 1 will be larger than K, so only 0 can be taken regardless of the jth digit of $ A_1 $ ~ $ A_N $ (where check is True). In that case, you can freely choose either 0 or 1). (↑ ** This operation is also used for digit DP with restrictions of K or less, so I thought it should be familiar **.)

You can find the answer by implementing the above idea and adding the maximum value (possible below K) in each digit to ans.

answerD.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
co=[0]*50
check=False
for i in range(49,-1,-1):
    for j in range(n):
        if (a[j]>>i)&1:
            co[i]+=1
    if (k>>i)&1:
        if co[i]>=n-co[i]:
            ans+=(co[i]*(2**i))
            check=True
        else:
            ans+=((n-co[i])*(2**i))
    else:
        if check:
            if co[i]>=n-co[i]:
                ans+=(co[i]*(2**i))
            else:
                ans+=((n-co[i])*(2**i))
        else:
            ans+=(co[i]*(2**i))
print(ans)