yukicoder contest 268 Review

result

Impressions

I think the minimum move was done. I think it was good that I could read the D problem without giving up. I was able to understand the B and C problems by looking at the answers, but I will skip this time because it was a solution that seems to be difficult to learn.

Problem A

Normally, I would like to consider DP for such a problem, but it is difficult because $ n $ is at most $ 10 ^ {18} $. Therefore, we will conduct the experiment thinking that it may have some kind of law **.

Also, when at coordinates $ x $, both $ x + 1 $ and $ x + 6 $ are game overmass, both $ x + 2 $ and $ x + 5 $ are game overmass, $ x + 3 If both $ and $ x + 4 $ are game overmass, then that $ x $ is also game overmass. Therefore, if you look at the game overmass above, ** game overmass will increase in order **. ** Experiment to think about how to increase the game overmass ** and the figure below.

If you write it out as above, when there is a set of game overmass, the squares that are ** 9 or more away from the smaller game overmass (✳︎) of that set will always be the game overmass **. Therefore, when the square (✳︎) exists at the coordinates of 10 or more, the game is over. Therefore, if there is a square (✳︎), No is output and exit. Also, to determine the existence of a set of game overmass, prepare a set structure b that manages the game overmass, and in order from the larger game overmass $ x $, $ x + 1, x + 3, x + 5 Find out if any of the $ is included in the $ b $.

Next, when the square of ** (✳︎) exists at the coordinates of 9 or less, ** searches for which square is the game over by square 9 → 1, and the newly created game over is in order of $ b $. All you have to do is store it and finally determine if $ b $ contains 1.

A.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
b=set(a)
for i in range(k-1,-1,-1):
    if a[i]<=9:
        break
    else:
        if a[i]+1 in b:
            print("No")
            exit()
        if a[i]+3 in b:
            print("No")
            exit()
        if a[i]+5 in b:
            print("No")
            exit()
for j in range(9,0,-1):
    if j in b:
        if j+1 in b:
            if j-3>=1:
                b.add(j-3)
        if j+3 in b:
            if j-2>=1:
                b.add(j-2)
        if j+5 in b:
            if j-1>=1:
                b.add(j-1)
if 1 in b:
    print("No")
    exit()
print("Yes")

B, C problem

I will skip this time.

D problem

I think it was the easiest problem this time.

Scores can be ** calculated for each bit ** as there are only bitwise or and bitwise and operations. In addition, there are only two initial values of each bit, 0 or 1, and if you ** pre-calculate the score for each bit **, you can only see all the bits when the initial value is given ** You can find it at. Therefore, the array for saving in the pre-calculation is set as check and $ check [i] [j]: = $ (score when the initial value of the $ i $ bit is $ j $, but $ j = 0,1 $) (✳︎). We will consider asking for this below.

Now, consider calculating the score by looking at $ a \ _i $ in order when you are looking at the $ i $ bit and its initial value is $ k $. Also, the integer that I have according to the problem statement is $ x $ (of course, $ x = k $ at the beginning). And when we see the $ j $ th integer (the $ i $ bit is represented as $ a \ _ {ji} $), we have the integer $ x $ (but the value of the $ i $ bit). Given that the operation to be performed is either $ and $ or $ or $. At this time, the change of $ x $ and the change of $ check [i] [k] $ are shown in the table below.

By making a table as above **, you can visually grasp $ x $ and the score in an easy-to-understand manner **, and simply loop around the variables $ i, k, j $. .. Also, if you have $ check [i] [j] $, you can easily calculate the query just by adding and raising power.

(✳︎)… To be exact, $ check [i] [j] \ times 2 ^ i $ is the score for that bit.

D.py

n,q=map(int,input().split())
a=list(map(int,input().split()))
check=[[0,0] for i in range(32)]
s=list(map(int,input()))
for i in range(32):
    #Whether the initial state is 0 or 1
    for k in range(2):
        x=k
        for j in range(n):
            if (a[j]>>i)&1:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
                else:
                    if x==0:
                        check[i][k]+=1
                        x=1
                    else:
                        check[i][k]+=0
                        x=1
            else:
                if s[j]==0:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=1
                        x=0
                else:
                    if x==0:
                        check[i][k]+=0
                        x=0
                    else:
                        check[i][k]+=0
                        x=1
#print(check)
t=list(map(int,input().split()))
for _ in range(q):
    z=t[_]
    ans=0
    for i in range(32):
        ans+=(check[i][(z>>i)&1]*(2**i))
        #print(ans)
    print(ans)

After the E problem

I will skip this time.