[PYTHON] AtCoder Beginner Contest 161 Review

This time's results

Impressions of this time

Last week's ABC was an on-parade of mistakes, but this week it worked. I used it for about 50 minutes due to the D problem, and it seemed that I would settle down on my usual performance, so I'm glad I was able to show my tenacity. There are still issues such as not being able to solve the E problem in time, so I would like to work harder.

Problem A

You just have to think about how it will be replaced if you perform the operations in order. I also discovered that by setting `print (z, x, y)`, it is possible to output with a space between z, x, y. I would like to use it from now on.

A.py

x,y,z=map(int,input().split())
print(z,x,y)

B problem

Since s is the total number of votes, it is sufficient to judge whether the number of s / 4m or more is m or more.

B.py

n,m=map(int,input().split())
b=list(map(int,input().split()))
s=sum(b)
a=[i for i in b if i>=s/(4*m)]
print("Yes" if len(a)>=m else "No")

C problem

If n is greater than or equal to k, replace n with n-k. If n is less than or equal to k, replace it with k-n. Also, if n is less than or equal to k, n remains less than or equal to k even if replaced with k-n. Therefore, the remainder of dividing by k does not change during the first operation, and does not change by n% k or k-n% k during the second operation. Therefore, you can output ``` min (n% k, k-n% k)` ``.

C.py

n,k=map(int,input().split())
n=n%k
print(min(n,k-n))

D problem

First I was writing a tree diagram. While writing the tree diagram, I realized that there might be a relationship between the i-th digit and the i + 1-th digit **. So, when I experimented with ** what happens in the 1st to 2nd digits **, it became as follows.

From the result of the experiment, if the run-run number is treated as a character string, if the ** number of "the absolute value of the difference between the i-digit run-run number and the i-th digit is 1 or less" is added to the back side of the i-digit run-run number. ** You can see that you can make the run-run number in the i + 1 digit. Also, as you can see from the above experiment, ** if the i-th digit is 0 or 9, there are two numbers to add to the end, otherwise there are three numbers **. (✳︎) Therefore, perform the above operation for each digit and store it in the array, ** when the total number of elements contained in the array exceeds k, end the above operation **, and k in it. Just ask for the second.

(✳︎)… During the contest, I added it to the front side as well, so I removed the duplicates with set. This is the first code. The second chord is a chord that is added only to the back side.

answerD.py

k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        y=int(x[0])
        if y==1:
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        elif 2<=y<=8:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
            ans[-1].append(str(y+1)+x)
        else:
            ans[-1].append(str(y-1)+x)
            ans[-1].append(str(y)+x)
        z=int(x[-1])
        if z==0:
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        elif 1<=z<=8:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
            ans[-1].append(x+str(z+1))
        else:
            ans[-1].append(x+str(z-1))
            ans[-1].append(x+str(z))
    ans[-1]=list(set(ans[-1]))
    d+=len(ans[-1])
l=len(ans[-1])
v=sorted([int(i) for i in ans[-1]])

print(v[k-(d-l)-1])

answerD_better.py

k=int(input())
ans=[[i for i in range(1,10)]]
d=9
while d<k:
    ans.append([])
    for i in ans[-2]:
        x=str(i)
        z=int(x[-1])
        ans[-1].append(x+str(z))
        if z<=8:
            ans[-1].append(x+str(z+1))
        if z>=1:
            ans[-1].append(x+str(z-1))
    d+=len(ans[-1])
ans[-1].sort()
print(ans[-1][k-d-1])

E problem

I see the commentary. I think it's a good question to solve when you forget it. When I saw this problem, I had a short-circuited idea of interval → "imos or cumulative sum". I think that thinking about how to solve a problem centered on such an algorithm is a way of thinking that prevents you from becoming stronger, so I would like to stop. This time, I think it was a problem that sounded a warning to such an idea. This is because ** all the basics use the algorithm when you want to reduce the amount of calculation by the greedy algorithm **. Here, we will consider using the greedy algorithm. (✳︎) Let's say you ** think about the days when you can work in order from the front ** for this problem. At this time ** What does the i-th chosen working day mean **? As stated in Answer, it is the earliest day you can choose when you choose the working day from the front. In other words, ** the i-th choice date only appears after that date **. On the contrary, ** Thinking about the working days from the back **, and the jth selected working day ** appears only before that day **. Also, note that the jth day counting from the back is the k-j + 1st day counting from the front because it works just k days. From the above, we have obtained the information that the i-th selected day from the front must be ** x-day or later and y-day or earlier **. If x <y, there are multiple candidates for the i-th day, but if ** x = y, there are no candidates other than x (= y) for the i-th day **. Therefore, you can find the answer by counting the days that you can work in order from the front and the back, and outputting only when the i-th working day from the front is the same. I am convinced of this problem, and if a similar problem appears, it seems that it can be reproduced, but it was a problem I wanted to tackle at first sight. I didn't have enough time to see the answer after the contest and I was disappointed, so I would like to make an effort ** to speed up overall ** so that I can solve the six questions firmly.

(✳︎)… The greedy algorithm is not an algorithm.

answerE.py

n,k,c=map(int,input().split())
s=input()
l=[-1]*k
r=[-1]*k
nowl=0
indl=0
while nowl<n and indl<k:
    for i in range(nowl,n):
        if s[i]=="o":
            l[indl]=i
            nowl=i+c+1
            indl+=1
            break
nowr=n-1
indr=k-1
while nowr>=0 and indr>=0:
    for i in range(nowr,-1,-1):
        if s[i]=="o":
            r[indr]=i
            nowr=i-c-1
            indr-=1
            break
for i in range(k):
    if l[i]==r[i]:
        print(l[i]+1)

F problem

Suppose $ k (\ neq $ 1) is a divisor of ** n **. Here, ** n is divided by k until it is not divisible by k **, and then ** n is replaced by nk ** (n mod k remains unchanged $ \ leftrightarrow $ n remains indivisible by k). Become. Therefore, if you think in the same way as the C problem, you can say that ** n mod k is 1 and finally n becomes 1 **. Also, if ** k is not a divisor of n, you can only replace n with n-k **, so you only need to check if n mod k is 1. Also, the reason why n mod k becomes 1 is that l * k + 1 = n $ \ leftrightarrow $ l * k = n-1 when the operation of replacing n with nk is performed l times. You can see that ** k should be a divisor of n-1 **. (✳︎) From the above, in the code below, refer to the code of make_divisors (I did not prepare the code for enumerating divisors myself, so this article) After finding all the divisors in (), we checked the above n mod k with each divisor as k. When I checked the code I wrote during the contest again, I found that the code was written fairly appropriately, so I would like to ** carefully consider it before writing the code.

(✳︎)… When k is not a divisor of n, it can be shown by reductio ad absurdum that k is a divisor of n-1.

answerF.py

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
n=int(input())
x=make_divisors(n)
l=len(x)
ans=0
for i in range(l):
    k=n
    if x[i]==1:
        continue
    while k%x[i]==0:
        k//=x[i]
    if k%x[i]==1:
        ans+=1

y=make_divisors(n-1)
l2=len(y)
ans2=0
for i in range(l2):
    k=n
    if y[i]==1:
        continue
    while k%y[i]==0:
        k//=y[i]
    if k%y[i]==1:
        ans2+=1
print(ans+ans2)

answerF_better.py

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors

def all_pattern(l):
    global n
    ans=0
    for ds in make_divisors(l)[1:]:
        k=n
        while k%ds==0:
            k//=ds
        ans+=(k%ds==1)
    return ans

n=int(input())
print(all_pattern(n)+all_pattern(n-1))