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

This time's results

スクリーンショット 2020-10-06 20.11.38.png

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.

Recommended Posts

Codeforces Round # 658 (Div. 2) Bacha Review (7/29)
Codeforces Round # 654 (Div. 2) Bacha Review (8/18)
Codeforces Round # 594 (Div. 2) Bacha Review (10/29)
Codeforces Round # 597 (Div. 2) Bacha Review (10/27)
Codeforces Round # 666 (Div. 2) Bacha Review (9/2)
Codeforces Round # 659 (Div. 2) Bacha Review (8/5)
Codeforces Round # 610 (Div. 2) Bacha Review (10/5)
Codeforces Round # 479 (Div. 3) Bacha Review (9/25)
Codeforces Round # 603 (Div. 2) Bacha Review (10/15)
Codeforces Round # 600 (Div. 2) Bacha Review (10/21)
Codeforces Round # 481 (Div. 3) Bacha Review (9/24)
Codeforces Round # 639 (Div. 2) Bacha Review (9/4)
Codeforces Round # 612 (Div. 2) Bacha Review (10/2)
Codeforces Round # 521 (Div. 3) Bacha Review (10/9)
Codeforces Round # 652 (Div. 2) Bacha Review (8/24)
Codeforces Round # 673 (Div. 2) Bacha Review (10/22)
Codeforces Round # 606 (Div. 3) Bacha Review (10/13)
Codeforces Round # 613 (Div. 2) Bacha Review (10/1)
Codeforces Round # 665 (Div. 2) Bacha Review (8/23)
Codeforces Round # 592 (Div. 2) Bacha Review (11/03)
Codeforces Round # 662 (Div. 2) Bacha Review (8/8)
Codeforces Round # 675 (Div. 2) Bacha Review (10/30)
Codeforces Round # 486 (Div. 3) Bacha Review (9/23)
Codeforces Round # 671 (Div. 2) Bacha Review (9/22)
Codeforces Round # 669 (Div. 2) Bacha Review (9/9)
Codeforces Round # 672 (Div. 2) Bacha Review (10/16)
Codeforces Round # 638 (Div. 2) Bacha Review (9/16)
Codeforces Round # 668 (Div. 2) Bacha Review (9/7)
Codeforces Round # 663 (Div. 2) Bacha Review (8/16)
Codeforces Round # 609 (Div. 2) Bacha Review (10/6)
Codeforces Round # 645 (Div. 2) Bacha Review (9/10)
Codeforces Round # 664 (Div. 2) Bacha Review (8/13)
Codeforces Round # 660 (Div. 2) Bacha Review (8/4)
Codeforces Round # 643 (Div. 2) Review
Codeforces Round # 679 (Div. 2) Review (10/25)
Codeforces Round # 657 (Div. 2) Review
Educational Codeforces Round 94 Bacha Review (9/3)
Educational Codeforces Round 91 Bacha Review (7/28)
Educational Codeforces Round 88 Bacha Review (8/4)
Educational Codeforces Round 86 Bacha Review (9/17)
Educational Codeforces Round 89 Bacha Review (9/8)
Educational Codeforces Round 92 Bacha Review (7/30)
Educational Codeforces Round 90 Bacha Review (8/19)
Educational Codeforces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
Codeforces Round # 626 B. Count Subrectangles