AtCoder ABC164 This is a summary of the AtCoder Beginner Contest 164 questions that were held on 2020-04-26 (Sun), starting with question A and taking into consideration the considerations. In the second half, we will deal with the problem of DEF (only D is properly summarized due to time constraints). Click here for the first half. The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF
Problem statement Given a string $ S $ consisting only of numbers from "1" to "9". A set of integers that satisfy the following conditions
(i,j) (1 \leq i \leq j \leq |S|) Find the total number of. Condition: If you look at $ S $ from the $ i $ character to the $ j $ character as a $ 10 $ decimal integer, this integer is a multiple of $ 2019 $.
At first, I thought that the constraint was $ (1 \ leq S \ leq 200000) $, so I was honestly TLE. The problem up to C was solved at a faster pace than usual, so I interpreted it conveniently. I got out of TLE, read the problem again, and was disappointed.
(1 \leq |S| \leq 200000)
I can't make it in time ... After that, I went to see the E and F problems and decided to use the remaining 90 minutes for this problem, but I couldn't solve it. Looking on Twitter after finishing, it seems that it is a similar subject of ABC158 E problem. After all, I keenly realized that growth cannot be expected without resolving problems that could not be solved firmly (ordinary people have no choice but to ask past questions and be able to solve similar problems, right? Sweat). I tried to read the explanations and put together an article by looking at past problems, but on April 28, @ Seika139 said, "[ABC164 D problem that can be understood even with a few numbers (modulo operation)](https: // I posted an article titled "qiita.com/Seika139/items/8cacdb3cc8fa6655573c)" and gently erased what I was writing. If there is such a cohesive article, I can't write it anymore (sweat) I also learned from this article as a reference. For the time being, I submitted the code with reference to the one published in "ABC164 D problem that can be understood even with a few numbers (modulo operation)".
abc164d.py
S = input()[::-1]
ans = 0
mods = [0] * 2019
mods[0] = 1
current = 0
x = 1
for s in S:
current = (current + x * int(s)) % 2019
ans += mods[current % 2019]
mods[current % 2019] += 1
x = x * 10 % 2019
print(ans)
Personally, I didn't know that the combination could be calculated with ʻans + = mods [current% 2019] `, so I learned it. Basically, it is necessary to count the number of combinations where $ D [j] = D [i] $ described in the referenced article, but I will calculate after $ n $ is decided. I only knew how to do it.
For example, $ i $ with $ D [i] = 5 $ has been found so far, and $ j (i \ not = j) $ with $ D [j] = 5 $ has been newly found. When
{}_{m+1} C _2 = {}_m C _2 + m
Therefore, it can be calculated by adding $ m $ ... I was ashamed to say that I didn't know. Now you don't have to calculate $ {} _n C _2 $ after you finish the calculation.
I felt like I didn't write it in the article I referred to, so I'd like to write it a little, but it's about the reason why mods [0] = 1.
This is about when $ D [i] = 0 $.
In the example given in the referenced article, $ D [i] = 0 $ does not appear, so I would like to end the D problem with two examples.
Input example 1 is when $ S = 18171 $. At this time, $ D [i] $ starts from $ i = 0 $.
Input example 2 is for $ S = 1817118171 $. At this time, $ D [i] $ starts from $ i = 0 $.
Only $ D [i] = 0 $ is special, and even if you do not select $ D [i] = 0 $ and $ D [j] = 0 $ in two places, only $ D [i] = 0 $ The numbers are different because they are divisible. In the article I referred to,
Assuming that the actual array $ D $ is $ N + 1 $ instead of $ N $ in length, prepare one empty room with $ D [N + 1] = 0 $. This has to do with the fact that there are $ {} _ {N + 1} C_2 $ ways to choose the indexes $ i, j $ that slice the string $ S $.
I think that it corresponds to here, but by adding the part that does not have $ D [N + 1] = 0 $, $ D [N + 1] = 0 $ and $ D [i Choosing a combination of] = 0 $ corresponds to choosing only $ D [i] = 0 $.
This makes it possible to calculate, so we set mods [0] = 1 to assume that there is $ D [N + 1] = 0 $ at the beginning.
In the actual contest, I don't feel like I'm so crazy about implementation ...
Problem statement There are $ N $ cities numbered from $ 1 $ to $ N $. These cities are connected by $ M $ railroad lines. You are currently in the city $ 1 $ with $ 10 ^ {100} $ gold coins and $ S $ silver coins. The $ i $ th rail line connects the city $ U_i $ and the city $ V_i $ in both directions, with a one-way fare of $ A_i $ silver coins and a travel time of $ B_i $. Fares cannot be paid in gold coins. Each city has a currency exchange office, where you can exchange $ 1 $ gold coins for $ C_i $ silver coins. The exchange costs $ D_i $ per $ 1 $ gold coin. You can exchange as many gold coins as you like at each exchange. For $ t = 2, ..., N $, find the minimum time it takes to move from city $ 1 $ to city $ t $. You can ignore the time it takes to wait for the train.
It seemed like a problem of applying the dijkstra method, but I'm not used to even the simple implementation of the dijkstra method in the first place, so I think I have to study that area from scratch. Among the submitted code, I referred to Code of Kiri8128 who was AC-passed with python first. @ kiri8128
abc164e.py
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, S = map(int, input().split())
k = 2451
X = [[] for _ in range(N * k)]
for _ in range(M):
u, v, a, b = map(int, input().split())
u, v = u-1, v-1
for i in range(a, k):
X[u * k + i].append([v * k + i - a, b])
X[v * k + i].append([u * k + i - a, b])
for i in range(N):
c, d = map(int, input().split())
for j in range(k - 1):
X[i * k + j].append([i * k + min(j + c, k - 1), d])
def dijkstra(n, E, i0=0):
h = [[0, i0]]
D = [-1] * n
done = [0] * n
D[i0] = 0
while h:
d, i = hpop(h)
done[i] = 1
for j, w in E[i]:
nd = d + w
if D[j] < 0 or D[j] > nd:
if done[j] == 0:
hpush(h, [nd, j])
D[j] = nd
return D
D = dijkstra(N * k, X, min(S, k - 1))
print(*[min(D[i * k:(i+1) * k]) for i in range(N)][1:], sep = "\n")
I'm still lacking in study, so I hope I can study slowly around here.
Problem statement Given an array $ S, T, U, V $ with an integer $ N $ and a length $ N $. Build one $ 1 $ matrix of $ N × N $ that meets the following conditions. ・ $ A_ {i, j} $ is an integer. ・ $ 0 \ leq a_ {i, j} \ leq 2 ^ {64} $ ・ When $ S_i = 0 $, the bitwise AND of the elements on the $ i $ line is $ U_i $. ・ When $ S_i = 1 $, the bitwise AND of the elements on the $ i $ line is $ U_i $. ・ When $ S_i = 0 $, the bitwise AND of the elements in the $ i $ column is $ V_i $. ・ When $ S_i = 1 $, the bitwise AND of the elements in the $ i $ column is $ V_i $. However, there may be cases where there is no matrix that meets the conditions.
Currently, neither D nor E has been solved, so I will try again someday (sweat) First of all, I have to go steadily from the place where it seems to be solved.
It seems that it is not possible to properly organize E and F every time. I hope I can start over when I have time. Thank you for reading the second half to the end.
Recommended Posts