[PYTHON] AtCoder Beginner Contest 117 Review of past questions

Time required

スクリーンショット 2020-04-14 18.19.47.png

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)

Recommended Posts

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