[PYTHON] AtCoder Beginner Contest 098 Review of past questions

Time required

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)