yukicoder contest 268 Review

result

スクリーンショット 2020-10-03 11.47.56.png

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.

IMG_0672.jpg

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.

IMG_0673.jpg

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.

Recommended Posts

yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 263 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
Keyence Programming Contest 2020 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
yukicoder contest 261 Participation record
AtCoder Beginner Contest 170 Review
AtCoder Regular Contest 104 Review
yukicoder contest 278 Participation record
yukicoder contest 262 entry record
AtCoder Beginner Contest 165 Review
yukicoder contest 248 Participation record
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review