Codeforces Round # 675 (Div. 2) Bacha Review (10/30)

This time's results

スクリーンショット 2020-10-31 8.39.22.png

Impressions of this time

I couldn't understand the problem statement of problem A well, and I made a silly mistake in the experiment of problem C, and I had a lot of trouble.

I need to switch over here the most, so I will practice repeatedly to improve the accuracy.

Problem A

A non-degenerate $ n $ polygon can be created by connecting the $ n $ points appropriately if they are not on a straight line. Also, since $ \ leftrightarrow $ (not on a straight line) (the longest edge is less than the sum of the other edges), $ d = a + b + c- for the given $ a, b, c $. It should be 1 $.

A.py


for _ in range(int(input())):
    x=list(map(int,input().split()))
    print(sum(x)-1)

Problem B

** It suffices if the palindrome is in the row and column directions **. Therefore, ** up to 4 places ** must have the same number. Also, for the $ (i, j) $ component, when $ n $ is odd and $ i = [\ frac {n} {2}] $, there is no component that needs to be the same number in the column direction, and $ m It is also ** note ** that when $ is odd and $ j = [\ frac {m} {2}] $, there are no components that need to have the same number in the row direction.

Therefore, according to the above rule, ** divide by component that has the same number (✳︎1) **, and then ** (✳︎) which component has the same number so that it is equal to the median. The number of operations can be minimized by operating +1 or -1. Therefore, the total of these should be the answer.

(✳︎1)… To separate the same components, just save the unchecked components in a matrix and scan the components of all the matrices.

(✳︎2)…f(x)=\sum_{i} |a\_i-x|To minimizea\_iTo the median when arranging in ascending orderxIt's time to do. I can prove this, but I will omit the proof because it is famous.

B.py


for _ in range(int(input())):
    n,m=map(int,input().split())
    mat=[list(map(int,input().split())) for i in range(n)]
    check=[[0]*m for i in range(n)]
    segments=[]
    for i in range(n):
        for j in range(m):
            if check[i][j]==0:
                seg_sub=[]
                check[i][j]=1
                seg_sub.append(mat[i][j])
                if n%2==0 or i!=n//2:
                    check[n-1-i][j]=1
                    seg_sub.append(mat[n-1-i][j])
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        check[n-1-i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                        seg_sub.append(mat[n-1-i][m-1-j])
                else:
                    if m%2==0 or j!=m//2:
                        check[i][m-1-j]=1
                        seg_sub.append(mat[i][m-1-j])
                segments.append(seg_sub)
    ans=0
    for i in segments:
        seg=sorted(i)
        m=len(seg)//2
        for i in seg:
            ans+=abs(i-seg[m])
    print(ans)

C Problem

(Hereafter, when the $ i $ digit is mentioned, it is 0-indexed and the value of that digit is $ s [i] $.)

For such problems ** it is good to consider the contribution of each digit **. When the $ i $ digit is $ 10 ^ k $ in $ i \ geqq k $, the contribution can be calculated from the figure below.

IMG_0732.jpg

From the above figure, the contribution is $ k \ times 10 ^ k \ times s [i] $. Therefore, for any $ i $ and $ k $:

\sum_{k=0}^{n-2} \sum_{i=k}^{n-1} k \times 10^k \times s[i] \leftrightarrow \sum_{k=0}^{n-2} k \times 10^k \sum_{i=k}^{n-1} s[i]

Therefore, ** the calculation of the inner sum does not depend on $ k , so it can be precalculated **, and the cumulative sum from the opposite side can be considered ( O (n) $). Also, if the pre-calculation is done, the outer sum can be calculated with $ O (n) $, so the total amount of calculation is $ O (n) $.

C.py


mod=10**9+7
s=list(map(int,input()))[::-1]
n=len(s)
if n==1:
    print(0)
    exit()
#10^k-th power
po=[1]
for i in range(n):
    po.append(po[-1]*10%mod)
#S_Cumulative from reverse i
si=[0]*n
si[n-1]=s[n-1]
for i in range(n-2,-1,-1):
    si[i]=si[i+1]+s[i]
ans=0
for k in range(n-1):
    ans+=((k+1)*si[k+1])*po[k]
    #print(ans)
    ans%=mod
for k in range(n-1):
    ans+=s[k]*((n-1-k)*(n-1-k-1)//2+(n-1-k))*po[k]
    #print(ans)
    ans%=mod
#print()
print(ans)

After D problem

I will not solve 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 # 609 (Div. 2) Bacha Review (10/8)
Codeforces Round # 597 (Div. 2) Bacha Review (10/27)
Codeforces Round # 666 (Div. 2) Bacha Review (9/2)
Codeforces Round # 651 (Div. 2) Bacha Review (8/20)
Codeforces Round # 659 (Div. 2) Bacha Review (8/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 # 618 (Div. 2) Bacha Review (9/26)
Codeforces Round # 648 (Div. 2) Bacha Review (9/5)
Codeforces Round # 676 (Div. 2) Bacha Review (10/31)
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 # 663 (Div. 2) Bacha Review (8/13)
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 93 Bacha Review (8/17)
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)
Codeforces Round # 609 (Div. 2) (up to B)
Educational Codeforces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B. Count Subrectangles