AtCoder ABC167 This is a summary of the problems of AtCoder Beginner Contest 167, which was held on 2020-05-10 (Sunday), in order from problem A, taking into consideration the consideration. 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 Takahashi is trying to register as a member of a certain Web service. First I tried to register the ID as $ S $. However, this ID was already in use by another user. Therefore, Mr. Takahashi considered registering a character string with $ 1 $ characters added to the end of $ S $ as an ID. Takahashi is trying to register a new ID as $ T $. Determine if this meets the above conditions.
I think that this area can be solved without any trouble if it is python.
I think you can write t [: -1] like t [: len (t) -1].
Both can create a string excluding the last character of the string.
--Example: "takaito" → "takait"
abc167a.py
s = input()
t = input()
if s == t[:-1]:
print("Yes")
else:
print("No")
Problem statement There are $ A $ cards with $ 1 $, $ B $ cards with $ 0 $, and $ C $ cards with $ -1 $. When you pick just $ K $ from these cards, what is the maximum possible value as the sum of the numbers written on the cards you picked?
In order to increase the possible value, we chose a card with $ 1 $ as much as possible, and considered that it is necessary to avoid choosing $ -1 $ as much as possible.
--If the number of cards you have to select is $ A $ or less, you can select the card with $ 1 $ written on it, so the maximum value is $ K $. --If the number of cards you have to select is $ A + B $ or less, you can select all the cards with $ 1 $ written on them and the rest with $ 0 $ written on them, so the maximum value Becomes $ A $. --If you have to select more cards, you need to select $ K-(A + B) $ for the $ -1 $ card, so $ A-(K-(A +) B)) $ is the maximum value.
All you have to do is implement conditional branching with an if statement.
abc167b.py
a, b, c, k = map(int, input().split())
if a >= k:
print(k)
elif a + b >= k:
print(a)
else:
print(a - (k - (a + b)))
It took about 6 minutes to solve the B problem, so I think I can solve it in my ideal time.
Problem statement Takahashi, who started competitive programming, has $ M $ of algorithms he wants to learn. Initially, the comprehension of each algorithm is $ 0 $. When Takahashi went to the bookstore, $ N $ of reference books were on sale. The $ i $ th reference book $ (1 \ leq i \ leq N) $ is sold for $ C_i $ yen, and by purchasing and reading, each $ j (1 \ leq j \ leq M) $ The understanding of the $ j $ th algorithm is increased by $ A_ {i, j} $. Also, you cannot improve your understanding in any other way. Takahashi's goal is to improve the understanding of all $ M $ algorithms to $ X $ or higher. Determine if Takahashi can reach the goal, and if possible, calculate the minimum amount required to reach the goal.
The constraint is small, $ 1 \ leq N, M \ leq 12 $.
There are two ways to buy the $ N $ reference book, "buy" or "do not buy", and there are a total of $ 2 ^ N $, so you can solve it with a full search.
I thought that I often use recursive functions when doing a full search.
Looking at the submission results of other "AC", surprisingly, there were many codes that did not use recursive functions.
I used a recursive function to create a vector (for example, $ [1, 0, 1, 1] $) indicating which book to buy, and used numpy to calculate the matrix.
The code I submitted received each line once in a list and divided it into a list of amounts and comprehensions, but on Twitter "I can receive it like this. c, * a = map (int, int, Only the part that receives the value is modified by referring to the description "input (). Split ()) ".
abc167c.py
import numpy as np
def func(ans, b_list, a_list, c_list, k, x):
if k == 0:
b_list = np.asarray(b_list)
x_list = np.dot(b_list, a_list)
if np.all(x_list >= x):
return np.inner(c_list, b_list)
else:
return ans
ans = min(ans, func(ans, b_list + [1], a_list, c_list, k - 1, x))
ans = min(ans, func(ans, b_list + [0], a_list, c_list, k - 1, x))
return ans
n, m, x = map(int, input().split())
c_list = []
a_list = []
for i in range(0, n):
c, *a = map(int, input().split())
c_list.append(c)
a_list.append(a)
ans = float("inf")
c_list = np.asarray(c_list)
a_list = np.asarray(a_list)
ans = min(ans, func(ans, [1], a_list, c_list, n - 1, x))
ans = min(ans, func(ans, [0], a_list, c_list, n - 1, x))
if ans == float("inf"):
print(-1)
else:
print(ans)
Recently, I feel that I'm having a hard time solving the problem of full search (sweat) Even if you understand the full search, it takes too long to implement, so you have to practice so that you can write smartly.
Problem statement There are $ N $ towns in the Kingdom of Takahashi. Towns are numbered from $ 1 $ to $ N $. Each town has $ 1 $ teleporters. The teleporter for town $ i (1 \ leq i \ leq N) $ is forwarded to town $ A_i $. King Takahashi likes the positive integer $ K $. Selfish King Takahashi wants to know which town he will arrive at if he starts from town $ 1 $ and uses the teleporter just $ K $ times. Create a program for this for King Takahashi.
Personally, I felt it was easier than the C problem. In particular, I have a strong feeling of being saved by the example (I immediately noticed that it looped).
Input example 2
6 7272022141732493516 5 2 5 3 2
In input example 2, starting from the town $ 1 $,
~ Policy ~
--Circulate the towns as instructed, add the order of the towns you visit to the list, and continue until you visit the same town. --If you visit the same town, count the number of teleports from the town $ 1 $ to the loop. --If the number of times $ K $ is less than entering the loop, the $ K $ th in the order list of the towns you visit is the answer. --If you are in a loop, the remainder of "$ K $" minus "the number of teleports from $ 1 $ in town to entering the loop" divided by the length of the loop is the final town. I know if I can arrive at.
Since the programming list (array) starts from 0, you need to be careful about that, but if you pay attention to it, I thought that implementation would not be so difficult, so I submitted the following code first.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
while True:
if next_machi in machi_list:
break
count += 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
However, the above code has a slow execution time, and I get "TLE" and despair. I wonder if the algorithm is wrong, is there a way to make it faster? I was confused. However, I couldn't think of any better method, so I felt that there was a problem with the implementation and reviewed it.
Possibly hungry for straw, I suspected that in the for statement ʻif next_machi in machi_list:` (there is a similar value in the list) to see if I visited the same town again. It was the part doing (I'm checking). This was a bad move. When the array became large, I thought it would take time to check everything, so I prepared a dict immediately. After rewriting the code as below, it passed "AC" safely.
abc167d.py
n, k = map(int, input().split())
x = list(map(int, input().split()))
count = 1
machi = 0
machi_list = [0]
next_machi = x[machi] - 1
machi_dict = {}
while True:
if next_machi in machi_dict:
break
count += 1
machi_dict[next_machi] = 1
machi_list.append(next_machi)
machi = next_machi
next_machi = x[machi] - 1
z = 0
for i in range(0, count):
if machi_list[i] == next_machi:
z = i
break
loop_machi_list = machi_list[z:]
if k < z:
machi = machi_list[k] + 1
print(machi)
else:
k = k - z
machi = loop_machi_list[k % len(loop_machi_list)] + 1
print(machi)
This "TLE" resonates with the ranking, so I wanted to acquire the minimum implementation power around here considering that I will use python in the future at work. The algorithms I learned in the competition pro are the jobs I will be involved in in the future, and it seems quite likely without them, but it is very educational to be able to experience heavy examples with such detailed implementation (list relations, etc.) In particular).
This is the end of the first half.
The momentary ranking when I finished solving the D problem was pretty good, but it wasn't good after that, so I need to study a little more. Thank you for reading to the end of the first half.
The second half will explain the EF problem. Scheduled to continue in the second half.
Recommended Posts