This is a review article for beginners of competition professionals.
The solution I write here was written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
A - ABC Swap
It is a problem to replace the contents of the three boxes with a fixed operation. Since the position of the swap operation is fixed from the beginning, just change the order of x, y, z to z, x, y and output.
x, y, z = map(int, input().split())
print(z, x, y)
B - Popular Vote
It is a problem to find out if there are M or more products that got a certain number of votes among N types of products.
We sorted the number of votes given and checked if the Mth product met the conditions. I passed by this.
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
if A[M-1] >= sum(A) / (4 * M):
print('Yes')
else: print('No')
C - Replacing Integer The question is to answer what the minimum value will be if you keep subtracting K from the given N.
The last remaining number after subtracting from the given number ... is equivalent to the calculation to find the surplus term. If you subtract one more, it will be the value obtained by subtracting K from the surplus term (minus).
I implemented it with the following code.
N, K = map(int, input().split())
print(min(N%K, K-N%K))
D - Lunlun Number
It is a problem to find the Kth number that satisfies the condition of the number of run-runs.
At first glance, the conditions seem simple, but I gave up because I didn't know how to efficiently find the K-th number.
I saw the commentary. In this problem, you can find it at high speed by adding a number that satisfies another condition to the right end of the number used once. The commentary did this by using cues.
First put a number from 1 to 9 in the queue. Take out the left end and set its value to $ x $. Let $ r $ be the ones digit of $ x $. If $ r $ is "0", calculate $ 10x, 10x + 1 $ and requeue them. Similarly, if $ r $ is "1 ~ 8", then $ 10x + (r-1), 10x + r, 10x + (r + 1) $, if r is "9", then $ 10x --1, 10x $ is calculated, and then again. To the queue.
By repeating this, the value extracted at the kth time is the number to be obtained.
I tried to implement it as it is.
K = int(input())
Q = [i for i in range(1, 10)]
for _ in range(K):
x = Q.pop(0)
r = x%10
if r != 0: Q.append(x*10 + r - 1)
Q.append(x*10 + r)
if r != 9: Q.append(x*10 + r + 1)
print(x)
This is TLE. The speed of pop () seems to be slow. I don't think I need to take it out, so I'll keep it as an array and turn it with for.
K = int(input())
Q = [i for i in range(1, 10)]
k = 0
for q in Q:
if k >= K:
break
r = q%10
if r != 0:
Q.append(q*10 + r - 1)
k += 1
Q.append(q*10 + r)
k += 1
if r != 9:
Q.append(q*10 + r + 1)
k += 1
print(Q[K-1])
I passed by this.
I was pointed out in the comments. Use the library properly when dealing with queues.
In python you can work with queues by using the collections.deque () class. There are functions such as ʻappend (), ʻappendleft (), pop (), popleft ().
import collections
K = int(input())
Q = collections.deque([i for i in range(1, 10)])
for _ in range(K):
x = Q.popleft()
r = x%10
if r != 0: Q.append(x*10 + r - 1)
Q.append(x*10 + r)
if r != 9: Q.append(x*10 + r + 1)
print(x)
E - Yutori
When you decide on working days and non-working days according to certain rules, it is a question to answer which day you always work.
I gave up and saw the commentary.
First of all, if you can afford to work for the quota, or if the quota is not enough, you will be out unconditionally.
So, let's consider the case where the number of working days is filled up to the last minute. First, create an array R that counts the days that you can work in order from the right end. This array contains the information "The $ x $ th working day is before $ R [x] $". Similarly, in the case of the array L that counts the working days in order from the left end, the information that "the $ x $ working day is after $ L [x] $" is included. Therefore, it can be said that the working day is always when $ L [x] $ and $ R [x] $ match.
The following code implements this. I passed by this.
N, K, C = map(int, input().split())
S = input()
L = []
R = []
holiday = 0
for i in range(N):
if holiday:
holiday -= 1
elif S[i] == 'o':
L.append(i)
holiday = C
holiday = 0
for i in range(N-1, -1, -1):
if holiday:
holiday -= 1
elif S[i] == 'o':
R.append(i)
holiday = C
R = R[::-1]
if len(L) == K:
for l, r in zip(L, R):
if l == r: print(l+1)
That's all for this article.
Recommended Posts