[PYTHON] AtCoder Beginner Contest 161 Review

This time's results

スクリーンショット 2020-04-05 11.06.28.png

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.

IMG_0176.PNG

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))

Recommended Posts

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions