[PYTHON] Codeforces Round # 654 (Div. 2) Bacha Review (8/18)

This time's results

Impressions of this time

This time, I was able to solve it with a very good feeling. However, I missed Gokan because I had lunch on the way. I am very disappointed. I feel that my senses are gradually being sharpened, so I would like to continue to do my best. I will do my best to aim for AtCoder Blue and Codeforces Purple, which are my goals during the summer vacation.

Problem A

If there are an even number, make a stick with a length of $ n + 1 $, and if there are an odd number, make a stick with a length of $ n $. At this time, make a stick with the same length. The number of sticks that become is $ [\ frac {n} {2}] $.

It can be proved by considering the sticks of the length that can be made in ascending order, but it is omitted here.

A.py

for _ in range(int(input())):
    n=int(input())
    print(-(-n//2))

Problem B

It is a problem that seems to be a trap, but you can reach the correct answer by carefully classifying each case.

First, consider choosing consecutive $ n $ days to connect, but ** one week ** always connects if $ n $ days is included, whereas ** multiple weeks ** If you straddle, $ n $ days may not be connected. Therefore, if a week is $ i (1 \ leqq i \ leqq r) $ days, consider the case of $ i \ geqq n $ and the case of $ i <n $.

(1) In the case of $ i \ geqq n $ When selecting consecutive $ n $ days to connect, it will be as shown in the figure below, and for any $ i $, its shape will match $ 1 $ when translated, so when $ r \ geqq n $, 1 When $ r <n $ on the street, there are 0 streets.

(2) When $ i <n $ When choosing consecutive $ n $ days to connect, be sure to span multiple weeks as shown below. Therefore, shapes that are not the same when translated can be ** distinguished in the first day ** of consecutive $ n $ days, resulting in $ i $ streets.

Also, since it is $ 1 \ leqq i \ leqq min (n-1, r) $, $ \ sum \ _ {i = 1} ^ {min (n-1, r)} i = \ _ {min (n, r) +1)} C \ _2 $ is the answer. Also, I made a mistake in the range of ** $ i $ ** I didn't fit the sample.

B.py

for _ in range(int(input())):
    n,r=map(int,input().split())
    if r<n:
        print(r*(r+1)//2)
    else:
        print(1+(n-1)*n//2)

C problem

The first type of guest is selected from the most cookies, and the second type of guest is selected from the least number of cookies. At this time, consider whether the order of the guests can be decided so that each guest does not have any cookies left when choosing a cookie.

First of all, the second type of guest ** seems to have few choices because they choose the smaller cookie **, so I want to keep as many cookies as possible. Therefore, I thought that it would be better to ** select the second type of guest first **, and think that the number of cookies that can be selected by the second type of guest is at most $ min (a, b) $. It was. Also, when the second type of guest chooses a cookie, ** the remaining number of the smaller cookies cannot be chosen twice **, so $ min (a, b) $ is the largest cookie to choose. It will be the number of sheets. Therefore, if it is $ m \ leqq min (a, b) $, the second type of guest can always choose the smaller cookie and leave the cookie. Also, there are $ (min (a, b) -m) + max (a, b) = a + bm $ cookies left in ** after the second guest has been selected, but the rest. Since the first type of guest can choose all of the cookies of, if it is $ a + bm \ leqq n $, the first type of guest can also choose the cookie. From the above, "No" should be output when $ m> min (a, b) $ or $ a + b <n + m $, and "Yes" should be output at other times.

C.py

for _ in range(int(input())):
    a,b,n,m=map(int,input().split())
    if m>min(a,b):
        print("No")
    elif n+m>a+b:
        print("No")
    else:
        print("Yes")

D problem

I personally like ** using symmetry ** because it gives better visibility (although my tastes may be different).

The problem is to make $ f (A) = (max (R) -min (R)) ^ 2 + (max (C) -min (C)) ^ 2 $ as small as possible. First of all, it is easy to understand if you consider the one-dimensional case, but by ** dividing the number of 1s as evenly as possible **, $ f (A) $ will become smaller.

Now consider arranging $ k $ 1's in order as evenly as possible in each row and column. Also, when distributing evenly, I thought about it while observing ** consciousness of symmetry ** and ** deciding some rules **. Furthermore, $ max (R) -min (R) $ and $ max (C) -min (C) $ do not become 0 when $ k % n! = 0 $, so ** set them to 1 respectively. Consider the desired placement **. Then, you can see that it can be arranged according to this rule by distributing in the order of ① → ② → ③ →… in the figure below.

First, in case of (1), I came up with the idea because it is a diagonal component and has high symmetry. Also, I thought that I should place 1 in the ** diagonal component ** (green part) next to it, but this time also $ max (R) -min (R) $ And $ max (C) -min (C) $ always change while keeping 0 or 1. This is because the ** rows and columns contained in the blue, green, and yellow components are $ n $ each and are all different **, so the sum will not be more than 2 larger than the other rows and columns. is. Therefore, it can be generalized that they should be arranged so that they are all different from each other, and they should be arranged in order in the diagonal components as in the above figure. Also, this component can be expressed as $ (i, (i + j) % n) $ in $ 0 \ leqq i, j \ leqq n-1 $, and $ i, j $ is moved in order to $ k $. All you have to do is output the one in which 1 is placed.

D.py

for _ in range(int(input())):
    n,k=map(int,input().split())
    ans=[[0]*n for i in range(n)]
    f=False
    for j in range(n):
        for i in range(n):
            if k==0:
                f=True
                break
            k-=1
            ans[i][(i+j)%n]=1
        if f:
            break
    r=[sum(ans[i]) for i in range(n)]
    mar,mir=max(r),min(r)
    c=[sum([ans[i][j] for i in range(n)]) for j in range(n)]
    mac,mic=max(c),min(c)
    print((mar-mir)**2+(mac-mic)**2)
    for i in range(n):
        print("".join(map(str,ans[i])))

E1 problem

I ate lunch and couldn't implement it, I'm sorry! !!

** It is supposed to beat all enemies **, so if you have $ x $ candies at the beginning, fight the $ i (0 \ leqq i \ leqq n-1) $ th enemy Sometimes I have $ x + i $ candies. Also, since you only need to have more candies than the enemy, the $ i $ th person can win ** if the enemy has ** $ x + i $ or less candies. Also, how to select such an enemy can be found by bisect_right if you ** sort the number of enemy candies ** (I issued 1WA without sorting ...). Also, since the person before the ** $ i $ th person has already selected $ i $ enemies **, the actual number of enemies that can be selected is "($ x + i $ or less candies). Number of enemies)-$ i $ "people. Also, if there is a person whose value is less than $ 0 $, there are 0 ways to select the enemy and it is divisible by $ p $, so it does not satisfy the theme. Also, when $ x \ geqq max (a) $, ** any enemy can be selected, so $ n! $ Street **, and when $ x <min (a) $, ** there is no selection method. From $ 0 $ street **, both are divisible by $ p $, so you should look for one that is not divisible by $ p $ in the range of $ min (a) \ leqq x <max (a) $. ..

E.py

n,p=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
ans=[]
from bisect import bisect_right
for i in range(min(a),max(a)):
    for j in range(n):
        b=bisect_right(a,i+j)-j
        if b<=0:
            break
        elif b%p==0:
            break
    else:
        ans.append(i)
print(len(ans))
print(" ".join(map(str,ans)))

After the E2 problem

I will skip this time