AtCoder ABC165 This is a summary of the AtCoder Beginner Contest 165 problems that took place on 2020-05-02 (Sat), starting with problem A and taking into account the considerations. The first half deals with problems up to ABCD. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement Jumbo Takahashi decided to practice golf. Jumbo Takahashi's goal is to make the flight distance a multiple of $ K $, but Jumbo Takahashi's range of flight distance is $ A $ or more and $ B $ or less. Output "OK" if the goal can be achieved, and "NG" if not.
When I read the problem at a glance, it was a problem of skipping more than a multiple of $ K $, and when I thought about using an inequality, I was wondering if I could make the flight distance a multiple of $ K $. For the time being, the constraint is also $ 1 \ leq A \ leq B \ leq 1000 $, so I implemented it using a for statement to solve it. Below is the code I submitted.
abc165a.py
k = int(input())
a, b = map(int, input().split())
flag = 0
for i in range(a, b + 1):
if i % k == 0:
flag = 1
break
if flag == 1:
print("OK")
else:
print("NG")
However, if the range of constraints is very wide, it will not be in time to search with the for statement, so refer to the commentary article.
How to find a multiple of the maximum $ K $ less than $ B $ and see if it is more than $ A $
I also tried to implement how to solve it after finishing. Below is the reimplemented code.
abc165a.py
k = int(input())
a, b = map(int, input().split())
x = b // k * k
if a <= x:
print("OK")
else:
print("NG")
To be honest, I am competing for the speed to solve the D problem, so for the time being, I try to solve the A problem by the method I first came up with during the contest.
Since the python operator // can output an integer truncated after the decimal point of the division result, x is a multiple of the maximum k less than or equal to b by the calculation of x = b // k * k. It becomes.
Problem statement Takahashi has deposited $ 100 $ Yen at AtCoder Bank. AtCoder Bank earns $ 1 $% of deposits each year (compound interest, rounded down to the nearest whole number). Assuming that the deposit amount does not change due to factors other than interest, how many years will it take for Takahashi-kun's deposit amount to exceed $ X $ Yen for the first time?
When I saw that the constraint of $ X $ was up to $ 10 ^ {18} $, I was quite impatient at first and tried to think about some ideas, but if I think about it carefully, even $ 10 ^ {18} $ will be within $ 10000 $ years. I felt like I could reach it, implemented it, and confirmed it in 3760. I thought I could afford it, and when I tried to check the example before submitting it, the input in Example 2 was $ 10 ^ {18} $. If you look at it first, you may have been able to shorten the time to solve it a little. Below is the implemented code.
abc165b.py
x = int(input())
y = 100
for i in range(1, 10000):
y = int(y * 1.01)
if y >= x:
print(i)
break
Problem statement Given the positive integers $ N, M, Q $ and the $ 4 $ integer pair $ (a_i, b_i, c_i, d_i) Q $ pair. Consider a sequence $ A $ that meets the following conditions. ・ $ A $ is a positive integer sequence of length $ N $. ・ $ 1 \ leq A_1 \ leq A_2 \ leq ⋯ \ leq A_N \ leq M $ The score of this sequence is defined as follows. ・ Sum of $ d_i $ for i that satisfies $ A_ {b_i} −A_ {a_i} = c_i $ ($ 0 $ if such $ i $ does not exist) Find the maximum score for $ A $.
At the time of the contest, I couldn't afford to calculate $ O (?) $. I want to solve the problem a little more and get a sense of whether or not I can do a full search. When I was thinking about a method to solve it, I was running out of time, so I switched to full search with "TLE" preparedness and implemented it. For the time being, this is the code that I implemented and submitted.
abc165c.py
n, m, q = map(int, input().split())
dict_list = {}
key_list = []
for i in range(0, q):
a, b, c, d = map(int, input().split())
key = tuple([a, b, c])
key_list.append(key)
dict_list[key] = d
def func(i, k, a_list):
if k == 0:
temp_score = 0
for key in key_list:
if key[2] == a_list[key[1]-1] - a_list[key[0]-1]:
temp_score += dict_list[key]
return temp_score
k = k - 1
max_score = 0
for j in range(i, m + 1):
max_score = max(func(j, k, a_list + [j]), max_score)
return max_score
score = 0
for i in range(1, m + 1):
score = max(func(i, n - 1, [i]), score)
print(score)
For the sequence $ A $ that is in ascending order, all patterns are created using a recursive function, and the maximum score is returned. This time, rather than implementing it, I would like to write a little part where there are $ {} _ {N + M−1} C _N $ sequences that satisfy the conditions. This type of problem is a problem that high school mathematics is always listed in the problem collection, and high school 1 starts to struggle. It looks like a problem of arranging numbers in a row, so I want to use $ P $, but it is a problem that I can use $ C $ to find the number of streets (I think it often appeared in mock exams).
The idea is a little different from the official explanation, but my interpretation is to think of $ N $ balls and $ M-1 $ partitions, and arrange them in a row first. This can be done by summing the number of balls and dividers and arranging them according to $ (N + M-1)! $, But due to the existence of duplication, $ N! $ And $ (M-1)! $ Must be divided by (a common permutation problem with duplicate characters). Therefore,
\frac{(N + M - 1)!}{N!(M - 1)!} = {}_{N+M−1} C _N
Therefore, you can use $ C $ to find the number of streets. Why can we find the number of $ N $ balls and the $ M-1 $ dividers in a row and the number of $ A $ sequences in ascending order? Specifically, $ N = 6, M = Let's take the case of 8 $ as an example.
It is okay if you think that it shows $ A_1, A_2, ..., A_N $ in order from the circle on the left, so Example 1 is
Considering the same as Example 1, the room 1, 3, 7, 8 is empty, and there are two in the rooms 4, 6, so the sequence $ A $ is
When I'm a cram school teacher, I'm often asked this question from high school 1, so it's quite easy to stumble.
Problem statement Given the integers $ A, B, N $. Find the maximum value of $ floor (Ax / B) −A × floor (x / B) $ for a nonnegative integer $ x $ less than or equal to $ N $. However, $ floor (t) $ represents the largest integer less than or equal to the real number $ t $.
For the time being, I thought that I couldn't enumerate all of them, but I submitted a program for all searches and it was "TLE" (I'm afraid I can't come up with such an easy implementation of all searches due to the D problem). After that, I looked at the formula and divided the cases based on what I found, and I solved it without any problems. The order of the if statements in the code is written in the order in which they were divided during the actual contest. I quickly realized that $ floor (Ax / B) $ was a monotonous increase in a broad sense, so I first divided the cases by $ N <B $. This is $ floor (x / B) = 0 $, which is easy to think about, so I think it's easy to come up with. Since it is a monotonous increase in a broad sense, it can be seen that $ X = N $ is the maximum. Next, it was clear by substituting that $ N = B $ becomes $ floor (Ax / B) −A × floor (x / B) = 0 $, so $ X = N-1 $ You can see that it is the maximum. After that, by specifically substituting $ X = B-1 $ etc., by classifying the cases according to the size of $ A $ and $ B $, write the following code and submit it, "AC I was able to issue.
abc165d.py
a, b, n = map(int, input().split())
max_score = 0
if n < b:
max_score = int(a * n / b) - a * (n // b)
elif n == b:
max_score = int(a * (n-1) / b) - a * ((n-1) // b)
elif a <= b:
max_score = a - 1
elif a >= b:
max_score = int(a * (b-1) / b) - a * ((b-1) // b)
print(max_score)
When I looked at the explanation, it came to a very simple conclusion, and I felt that I was lacking in ability. When I implemented the conclusion of the explanation, I could write it with the following code (overwhelmingly short).
abc165d.py
a, b, n = map(int, input().split())
x = min(b - 1, n)
print(int(a * x / b) - a * (x // b))
This is the end of the first half.
In this contest, after solving the ABD problem, I didn't realize that the C problem was a full search problem, and I spent too much time on how to solve it, so I didn't have time to use it for the E and F problems, so I started with the D problem. I want to be able to solve it in about 40 minutes. Thank you for reading to the end of the first half for the time being.
The second half will explain the EF problem. Scheduled to continue in the second half.
Recommended Posts