This time's results

Impressions of this time

I think it went well this time. However, I am disappointed because I could not solve the D problem that seemed to be solved in time due to the overlap with lunch. However, it seemed that I could solve the problem at that level, so I thought I had grown a little. This time, I was able to deal with the problem calmly, so I think that is the reason for the victory.

Problem A

Based on the given values of $ r, g, b, w $, it is judged whether or not it becomes a palindrome when each character is arranged. Also, you can select $ r, g, b $ one by one and change them to $ w $ as much as possible, but ** this operation does not change the evenness of each if you do it twice **, so this You only have to think about two ways to do it once or not.

Under this, when the sum of the values of $ r, g, b, w $ (the length of the palindrome) is even, any value of ** $ r, g, b, w $ is even **. If you have one, you can make it. Also, by changing $ r, g, b $ to $ w $ once, the even and odd numbers of ** $ r, g, b, w $ are reversed **, so $ r, g, b, w $ You can make a palindrome if any value is odd.

On the other hand, when the length of the palindrome is odd, only one of ** $ r, g, b, w $ needs to be odd **. Also, considering the inversion of even and odd numbers, it is possible to make a palindrome even if only one of $ r, g, b, w $ is even.

`A.py`


for _ in range(int(input())):
    r,g,b,w=map(int,input().split())
    if (r+g+b+w)%2==0:
        if r%2==0 and g%2==0 and b%2==0 and w%2==0:
            print("Yes")
        elif r%2==1 and g%2==1 and b%2==1 and w%2==1:
            print("Yes")
        else:
            print("No")
    else:
        x=[r%2,g%2,b%2,w%2]
        if x.count(1)==1:
            print("Yes")
        elif x.count(0)==1 and r>0 and g>0 and b>0:
            print("Yes")
        else:
            print("No")

Problem B

Think of playing chess like a rook and following the squares on any grid. Even if you follow the dark clouds, the 埒 will not open, so consider ** following in some order **.

At first I thought I would follow the swirl, but I found it cumbersome to implement, so I thought ** I would follow it line by line **. In other words, consider following as shown in the figure below.

Here, only (1) after tracing all the upper rows ** and continuing to trace back to the lower row ** and (2) ** when moving between rows, you must move ** by the tangent square. Just be careful, the implementation looks like this:

① can be implemented by concatenating with list (range (x, -1, -1)) + list (range (x + 1, n)), and ② is whether the squares in contact are the leftmost column or the rightmost column. It can be implemented by dividing the case with.

`B.py`


n,m,x,y=map(int,input().split())
x-=1;y-=1
ans=[]
ans.append([x,y])

now=0
for i in list(range(x,-1,-1))+list(range(x+1,n)):
    now=1-now
    if i==x:
        ans+=[[i,j] for j in range(m) if j!=y]
    else:
        if now:
            ans+=[[i,j] for j in range(m)]
        else:
            ans+=[[i,j] for j in range(m)][::-1]
for i in ans:
    print(i[0]+1,i[1]+1)

C problem

At first, I thought about deciding not to set bits in order from the upper digit, but I felt that it would be difficult to greedily decide in the middle digit **.

When choosing something (number) like this problem, the outlook often improves when considering DP . Furthermore, it is also a decisive factor that bit calculation that makes it easy to save states and that or for each bit from $ 0 \ leqq a_i, b_i <2 ^ 9 $ takes only this range ( limit on the number of states **). Therefore, consider the following DP.

$ dp [i] [j]: = $ (Is there a case where it is $ j $ when taking or for each bit up to $ a_i $)

Considering such DP, if $ b_k (1 \ leqq k \ leqq m) $ is selected for $ a_i $ when $ dp [i-1] [j] = 1 $, it is as follows. Will be.

dp[i][j\|(a\_i \\& b\_k)]=1

Therefore, this DP can be calculated in about $ n \ times m \ times 2 ^ 9 $ times, so you can write a sufficiently fast program.

`C.py`


n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
change=[[a[i]&b[j] for j in range(m)]for i in range(n)]
dp=[[0]*(2**9) for i in range(n)]

for i in range(n):
    if i==0:
        for k in range(m):
            dp[0][change[i][k]]=1
        continue
    for j in range(2**9):
        if dp[i-1][j]==1:
            for k in range(m):
                dp[i][j|change[i][k]]=1

for j in range(2**9):
    if dp[-1][j]==1:
        print(j)
        break

D problem

At first I misunderstood the problem and thought I would just handle the array $ a $. ** If you look at the sample, you shouldn't have made a mistake **, so reflect on it and make use of it next (in this case, you can solve it by using DP).

First of all, it is self-evident that you want to select from the largest one. At this time, in the case of $ a \ _i> m $, it will not be possible to select it in the subsequent $ d $ day, so first divide it into the ** $ a \ _i> m $ element and the $ a \ _i \ leqq m $ element. ** Store in the array ʻe, f. Also, it is assumed that ʻe and f are arranged in descending order.

Here, if you know the number of elements that are ** $ a \ _i> m $, you can know the number of elements that can be selected from the elements that are ** $ a \ _i \ leqq m $, so ** $ a \ _i Let's assume that there are $ k $ elements that are> m $ **. Also, as you can easily see, $ k $ is less than or equal to len (f). Here, considering that $ k $ $ a \ _i (> m) $ should be arranged so that $ a \ _i (\ leqq m) $ can be selected as much as possible, the following arrangement is optimal.

Therefore, at this time, $ a \ _i (\ leqq m) $ can be selected for $ n- $ {$ (k-1) \ times (d + 1) + 1 $}. Also note that $ (k-1) \ times (d + 1) + 1 \ leqq n $ must be satisfied (the maximum $ k $ that satisfies this is $ K'$). .. Furthermore, even if ** $ n- $ {$ (k-1) \ times (d + 1) + 1 $} exceeds len (e), only those included in ʻe` can be selected (✳︎). ) ** Please note.

Also, if you increase ** $ k $ by 1, the number that can be selected from ʻe decreases by $ d + 1 $ **, so ** $ k $ to $ 0 $ ~ $ K'$ while managing the difference ** Look for the largest number of them. Also, $ k = 0 \ rightarrow 1 $ increases by $ 1 $ instead of $ d + 1 $, so consider $ k = 0 $ separately. At this time, you should consider the sum of ʻe.

In this way, the maximum value obtained for each $ k $ should be output as the answer.

(I noticed later, but I think that the implementation of (✳︎) was clearer if I tried to reduce ** $ k $ **.)

`D.py`


n,d,m=map(int,input().split())
a=list(map(int,input().split()))
e,f=[i for i in a if i<=m],[i for i in a if i>m]
e.sort(reverse=True)
f.sort(reverse=True)
c=len(e)
if c==n:
    print(sum(a))
    exit()
#a[i]>m can be selected appropriately up to max
l=1
r=min((n-1)//(d+1)+1,len(f))
#k's range 
#e,f 's sum
ans=sum(e)
nowe,nowf=0,0
for i in range(l,r+1):
    if i==l:
        nowe=sum(e[:n-(1+(l-1)*(d+1))])
        nowf=sum(f[:l])
        ans=max(nowe+nowf,ans)
        continue
    nowe-=sum(e[n-(1+(i-1)*(d+1)):n-(1+(i-1-1)*(d+1))])
    nowf+=f[i-1]
    ans=max(nowe+nowf,ans)
print(ans)

After the E problem

I will skip this time

Codeforces Round # 664 (Div. 2) Bacha Review (8/13)