[PYTHON] AtCoder Beginner Contest 121 Review of past questions

Time required

Impressions

Since the D problem was XOR, I thought it was impossible, but it was not so difficult and I felt that I was not enthusiastic. (Familiarity not enthusiastic)

Problem A

Just be careful about counting the places you wear.

answerA.py

H,W=map(int,input().split())
h,w=map(int,input().split())
print(H*W-h*W-w*H+h*w)

B problem

Each evaluation formula should be given for all problems.

answerB.py

n,m,c=map(int,input().split())
b=list(map(int,input().split()))
ans=0
for i in range(n):
    a=list(map(int,input().split()))
    k=0
    for i in range(m):
        k+=a[i]*b[i]
    ans+=(k+c>0)
print(ans)

C problem

Take as much as you can in ascending sort. It is necessary to accurately judge how much can be taken.

answerC.py

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort()
ans=0
for i in range(n):
    if m>ab[i][1]:
        ans+=ab[i][0]*ab[i][1]
        m-=ab[i][1]
    else:
        ans+=ab[i][0]*m
        print(ans)
        break

D problem

Postscript (2020/1/29)

** Added the code implemented by the Writer solution method. It is written near the end of the article. The writer solution is more versatile. ** **

In the XOR calculation, ** each bit can be calculated independently **, and when considering the XOR of the integers $ c_1 $ ~ $ c_n $, convert it to a binary number and count the number of 1s for each bit. Therefore, when the number of 1s is odd, it can be calculated as 1, and when it is even, it can be calculated as 0. In other words, even in this problem, it is sufficient to pay attention to each bit of A to B and calculate independently. First, let's think about the case where A to B are all converted to binary numbers and arranged in ascending order. At this time, you can see that it looks like the figure below.

If you look at how many 0s and 1s are in each bit, you can see that ** each bit periodically repeats 0s and 1s **. It is clear (without thinking?) That the length of this cycle will be $ 2 ^ {k} $ for the kth bit (0-indexed). Also, when k> = 1, the length of one cycle is even, so if you calculate XOR, one cycle will be 0, so you can ignore it. ** How many 1s are consecutive at both ends of A and B? It is good to count ** (the image of counting the part left in the odd number, when k = 1, only 0 and 1 are repeated, so the number of 1 can be easily obtained). Also, when some bits of A and B are different, you can simply calculate how many 1s to 1s there are on one side, but if both A and B are 1s in that bit, all 1s in A to B Please note that it will be double-counted (included in the same cycle) when it becomes. Also, when considering how far 1s continue from the end, you can easily think about how many 1s there are by considering the difference if you think as shown in the figure below (considering the boundary).

When the above is implemented, it becomes as follows.

Also, since it is a little unorganized, the flow of thought is organized below.

** (1) XOR, so just count how many 1s there are in each bit ↓ (2) There are (continuous) 0 and 1 cycles ↓ (3) Count how many 1s there are from the end (because the period length is even) ↓ (4) (3) can be understood by considering the number of boundaries at which the period switches **

Also, note that when b = 0, the argument of log2 becomes 0 and becomes RE. I got caught.

answerD.py

import math
import sys
a,b=map(int,input().split())
if b==0:
    print(0)
    sys.exit()
n=math.floor(math.log2(b))+1
ans=[0]*n
form="0"+str(n)+"b"
sa=format(a,form)
sb=format(b,form)
for i in range(n):
    if i==n-1:
        if (b-a+1)%2==0:
            ans[i]=((b-a+1)//2)%2
        else:
            if sa[i]=="1":
                ans[i]=((b-a+1)//2+1)%2
            else:
                ans[i]=((b-a+1)//2)%2
        break
    if sa[i]=="1" and sb[i]=="0":
        s_compa=sa[:i]+"1"*(n-i)
        cmpa=int(s_compa,2)
        ans[i]=(cmpa-a+1)%2
    elif sa[i]=="0" and sb[i]=="1":
        s_compb=sb[:i]+"1"+"0"*(n-i)
        cmpb=int(s_compb,2)
        ans[i]=(b-cmpb+1)%2
    elif sa[i]=="1" and sb[i]=="1":
        s_compa=sa[:i]+"1"*(n-i)
        cmpa=int(s_compa,2)
        s_compb=sb[:i]+"1"+"0"*(n-i)
        cmpb=int(s_compb,2)
        if cmpa>a:#cmpb<b
            ans[i]=((b-cmpb+1)+(cmpa-a+1))%2
        else:
            ans[i]=(b-a+1)%2
cnt=0
for i in range(n):
    cnt+=(ans[i]*2**(n-i-1))
print(cnt)

Writer solution

When calculating XORs of multiple numbers, convert them to binary numbers and count how many 1s there are for each bit. When the number of 1s is odd, it is 1 and when it is even, it is 0. It can be calculated in bits. From this, we can see that the result of XOR is 1 because the XOR is actually ** for consecutive two integers k and k + 1 (k is an even number) except for the 0th bit. Therefore, it is not necessary to consider all XORs from A to B in order, but by counting the pairs (k, k + 1) (k is an even number) from A to B and considering the total evenness of the pairs. You can easily find the XOR from A to B. However, at this time, the cases were divided by paying attention to whether A and B were included in the set. The code looks like this:

answerE_better.py

a,b=map(int,input().split())
if a%2==0 and b%2==0:
    k=(b-a)//2
    print(b^(k%2))
elif a%2==0 and b%2==1:
    k=(b-a+1)//2
    print(k%2)
elif a%2==1 and b%2==0:
    k=(b-a-1)//2
    print(a^b^k%2)
else:
    k=(b-a)//2
    print(a^(k%2))