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.
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)
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")
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))
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])
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)
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