AtCoder Beginner Contest 098 Review of past questions

Time required

スクリーンショット 2020-04-09 13.31.30.png

Impressions

In the past, I couldn't solve the XOR problem, but once I learned the basics that it would be easier to calculate by dividing each digit in binary, I could solve it. The explanation and code of D are difficult to understand, so I am waiting for improvement suggestions.

Problem A

Simply find max.

answerA.py


a,b=map(int,input().split())
print(max(a+b,a-b,a*b))

B problem

There are N-1 ways to divide into x and y, and for each of them, by making x and y a set instead of a string, the size of the largest intersection is the answer.

answerB.py


n=int(input())
s=input()
ans=0
for i in range(n-1):
    s1=s[:i+1]
    s2=s[i+1:]
    s3=set(s1)&set(s2)
    ans=max(ans,len(s3))
print(ans)

C problem

When deciding on a leader, you can count the number of people west of that leader who are facing west and those who are east of that leader who are facing east, but the number of people is O ( Must be calculated by 1) or O (log (n)). Here, since the number of people is ** cumulative sum **, it can be calculated by O (1) by calculating the number of people facing west and the number of people facing east as the cumulative sum.

answerC.py


n=int(input())
s=input()
l=[0]*n
r=[0]*n
for i in range(1,n):
    l[i]=l[i-1]+(s[i-1]=="W")
for i in range(n-2,-1,-1):
    r[i]=r[i+1]+(s[i+1]=="E")
ans=n-1
for i in range(n):
    ans=min(ans,l[i]+r[i])
print(ans)

D problem

First of all, I thought about paraphrasing because xor becomes equal to +. Then, in XOR, I noticed that there is no carry ** because the number of 1s in each digit is 1 when it is odd and 0 when it is even when it is converted to binary. Therefore, when adding **, if there is no carry for all digits **, we know that the subject is satisfied. Also, in other words, there is no carry in the i-th digit **, which is equivalent to the fact that the number of $ A_l… A_r $ such that the i-th digit is 1 is one or less **. I will. From the above, first prepare an array that stores the number of 1's in each digit. Based on this, we search for candidates for l and r, but considering whether $ A_l… A_ {r + 1} $ holds when $ A_l… A_r $ holds, $ A_l… A_r $ and $ A_l… A_ { When paying attention to each digit of r + 1} $, the number of ** 1 is either increased or unchanged **. Therefore, when l is fixed, the set of (l, r) that does not exceed 2 considering the number of 1s in each digit of $ A_l… A_r $ for r = l + k (k> = 1) is the subject. Meet. Also, if you use the ** scale method ** at this time, you can count all (l, r) candidates by moving ** r and then l ** to satisfy the subject. I will. Since I forgot how to implement the scale method, I will review the code of the scale method, but for details, refer to Kenchon's article. please. The important thing about this problem is that when ** (l, r) holds, then (l + 1, r) also holds ** (as you can see from the discussion so far). Therefore, when taking the scale, when l is fixed and r is increased while satisfying the subject, ** (l + 1, r) also holds for all r **. Therefore, it is possible to efficiently turn l by turning 0 → n-1 by turning the for statement, and holding and increasing r separately from the for statement. By the way, Python did not pass even with this scale method, so I passed it with PyPy.

The explanation is difficult to understand and the code is a little difficult to understand, so please let me know if you have any suggestions for improvement.

Postscript (2020/04/11)

Considering the case where there is no carry for all digits, the results of the + operation and the ^ operation are the same, so by saving the results of the + operation and the ^ operation respectively, "for each digit" It can be used as an alternative to an array that stores how many 1's there are (this way you can also run it in Python, see the comments for more information). Also, the second code is implemented this way.

answerD.py


n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
now=[0]*20#2^Because it is 20
for i in range(n):
    left=i
    if i!=0:
        for j in range(20):
            if (a[left-1]>>j)&1:
                now[j]-=1
    else:
        for j in range(20):
            if (a[left]>>j)&1:
                now[j]+=1
    while all([now[j]<=1 for j in range(20)]):
        right+=1
        if right==n:
            break
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]+=1
    else:
        for k in range(20):
            if (a[right]>>k)&1:
                now[k]-=1
    right-=1
    ans+=(right-left+1)
print(ans)

answerD2.py


n=int(input())
a=list(map(int,input().split()))
ans=0
right=0
np,nx=a[0],a[0]
for left in range(n):
    while np==nx:
        right+=1
        if right==n:
            break
        np+=a[right]
        nx^=a[right]
    else:
        np-=a[right]
        nx^=a[right]
    right-=1
    ans+=(right-left+1)
    np-=a[left]
    nx^=a[left]
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 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 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 053 Review of past questions
AtCoder Beginner Contest 094 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 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions
AtCoder Beginner Contest 122 Review of past questions
AtCoder Beginner Contest 125 Review of past questions
AtCoder Beginner Contest 109 Review of past questions
AtCoder Beginner Contest 118 Review of past questions