[PYTHON] Codeforces Round # 609 (Div. 2) Bacha Review (10/6)

This time's results

Impressions of this time

I tried to correct the misreading from yesterday, but I misread it due to C problem. It's too tight ... ** If you can't solve it in 30 minutes, you may need the courage to cut it quickly **.

Problem A

I will make it conveniently. Since it is a subtraction of numbers, ** pay attention to evenness **.

When $ n $ is even, both $ a and b $ are even, so if $ b = 4 $, for example, $ a $ is an even number larger than $ 4 $, so the subject is satisfied.

When $ n $ is odd, one of $ a and b $ is even and the other is odd. For example, if $ b = 9 $, $ a $ is an even number larger than $ 9 $, so the subject is satisfied.

A.py

n=int(input())
if n%2==0:
    print(n+4,4)
else:
    print(n+9,9)

Problem B

You can sort them, so you can think about how many remainders there are in ** $ a $ and $ b $ **, and solve the problem assuming that the answer is always valid under the constraint. Also note that $ m $ is up to 10 ^ 9 ways, so adding 1 at a time requires $ 10 ^ 9 $ calculations in time.

In the initial state, the element is saved in the dictionary in the form that there are $ y $ in the remainder of $ x . Also, since we want to save in ascending order of remainder, save the array of (remainder, number) pairs in ascending order of remainder ( c, d ) after generating the dictionary ( c, d $ are $ respectively). Corresponds to a and b $.). At this time, the lengths of $ c and d $ are equal and do not exceed $ n $.

At this time, add $ x $ to each element and divide by $ m $ to find the minimum $ x $ required for the set $ a $ and $ b $ of the remainder to match. Here, pay attention to the last element of ** $ a $ (the remainder is the largest) **, and when adding several numbers, the next set that may match is the first of ** $ b $. When it matches the element of (the remainder is the smallest) **. Therefore, remove the last element of $ a $ and add it again as the first element of $ a $ to find the difference ** needed to do that. In addition, the initial value is $ x = 0 $, the difference is added to $ x $ in order, and $ x $ when $ a and b $ are added until they match is output.

B.py

from collections import Counter
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
#0,1,Sort by the remainder of ...
#just shift a to match this
#At most n times
c=sorted([list(i) for i in list(Counter(a).items())],key=lambda x:x[0])
d=sorted([list(i) for i in list(Counter(b).items())],key=lambda x:x[0])
n=len(c)
#Delete the back and stick it to the front(Difference management)
x=0
for i in range(n):
    p=c.pop(-1)
    #It may not be necessary to go around
    dp=(d[0][0]+m-p[0])%m
    x+=dp
    c.insert(0,p)
    #print(c,d)
    for j in range(n):
        c[j][0]+=dp
        c[j][0]%=m
    if c==d:
        print(x%m)
        break

C problem

I misread it and swamped ...

(The $ i $ digit (0-indexed) from the top of the given number is $ a \ _i $, and the $ i $ digit from the top of the final number is $ b \ _i $. .)

$ a \ _i = a \ _ {i + k} $ makes a ** mysterious misreading ** that it holds only at a distance of $ k $, and $ a \ _i = a \ _ {i + 2k} $ I thought it didn't have to be. why….

When $ a \ _i = a \ _ {i + k} $ holds, the equivalent paraphrase is that all digits with the same remainder after dividing by ** $ k $ have the same value **. Therefore, if you decide $ b \ _i = a \ _i $ in $ 0 \ leqq i \ <k $, $ b \ _i $ will be uniquely determined for $ i \ geqq k $.

Now, pay attention to the digit that becomes $ b \ _i \ \ neq a \ _i $ when looking at $ i \ geqq k $ from the smaller side of $ i $. That is, if ** $ b \ _i > a \ _i $ appears first, then $ b> a $ holds **. Also, there is no $ b $ smaller than this, so we will output this as the answer. Conversely, if ** $ b \ _i \ <a \ _i $ appears first, ** must increase one of the digits by +1. Also, if +1 is added, all digits with the same remainder divided by $ k $ will be incremented by +1. ** No matter which remainder digit is added by +1 _i> a \ _i $ holds **. Therefore, it is best to add +1 to the $ i $ digit where $ i \ % \ k = k-1 $ holds, and $ b> a $ holds. Furthermore, if there is no digit that becomes $ b \ _i \ \ neq a \ _i $, then $ b = a $, so the subject is satisfied.

C.py

#I will look at the remainder

#I misunderstood all the subjects
#I thought it was only once
n,k=map(int,input().split())
a=list(map(int,input()))
ans=[-1]*n
upper=False
lower=False
#Updates occur in lower and upper
#Is it okay for the update to happen?
for i in range(k):
    ans[i]=a[i]
for i in range(k,n):
    ans[i]=ans[i-k]
    if ans[i]==a[i]:
        pass
    elif ans[i]>a[i]:
        #When it becomes upper first
        #You don't have to change
        if lower==False and upper==False:
            upper=True
    else:
        #When becoming lower first
        #Just change the lower part
        #Will it exceed if changed?
        if lower==False and upper==False:
            lower=True
            #Change the one who did the best
            #9 is no good
            #Below that is 0
            for j in range(k-1,-1,-1):
                if ans[j]!=9:
                    break
            for l in range(i+1):
                if l%k==j:
                    ans[l]+=1
                elif l%k>j:
                    ans[l]=0

print(n)
print("".join(map(str,ans)))

D problem

I thought about DP and a good configuration method, but it seems that it was a knowledge problem. I think it can't be helped if this is dropped.

** It seems that it is best to spread dominoes in a checkered pattern ** (Reference).

When you make a checkered pattern painted in black and white, you can see that it is less than or equal to min (the number of white squares, the number of black squares) (✳︎). Furthermore, the answer is to find the maximum value, which can be shown to be min (number of white cells, number of black cells). See here for proof. I think it's shown in an intuitive way.

D.py

n=int(input())
a=list(map(int,input().split()))
#I don't know
#Spreading dominoes → Apply in a checkered pattern(What?)
w,b=0,0
for i in range(n):
    if i%2==0:
        w+=a[i]//2
        b+=a[i]-a[i]//2
    else:
        b+=a[i]//2
        w+=a[i]-a[i]//2
print(min(b,w))

After the E problem

I will skip this time.