AtCoder Beginner Contest 121 Review of past questions

Time required

スクリーンショット 2020-01-20 14.39.41.png

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.

IMG_0096.JPG

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).

IMG_0095.JPG

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))

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 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 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
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions