This is a review article for beginners of competition professionals.
The solution I write here is written while looking at the commentary and other people's submissions. It may not be what you actually submitted.
S sheep and W wolves, winning is a question to be asked.
If S is more than W, the sheep will not be attacked.
S, W = map(int, input().split())
if S > W:
print('safe')
else:
print('unsafe')
It is a question to answer which one will win if the attack power B with physical strength A and the attack power D with physical strength C hit each other.
Takahashi-kun and Aoki-kun each need the number of attacks rounded up to $ C / B $ and $ A / D $. The one with the smaller number wins. Also, if the numbers are the same, Takahashi, who can be beaten first, is advantageous.
I implemented it with the above idea. I used math.ceil () for the round-up process. If you write something like (C + (B-1)) // B, you don't need a library.
import math
A, B, C, D = map(int, input().split())
if math.ceil(C/B) <= math.ceil(A/D):
print('Yes')
else:
print('No')
It is a problem to count how many kinds of character strings $ S_i $ are input N times.
I put it in a set type object and counted the length.
N = int(input())
S = [input() for _ in range(N)]
print(len(set(S)))
It is a question to answer how many numbers can be made divisible by 2019 when the input number S is cut out in an arbitrary interval.
I thought it was a similar subject to this and wrote the following code. (Actually, I couldn't do it during the contest because I made a mistake or couldn't shorten the time.)
import collections
S = input()
N = len(S)
M = [0]
mod = 0
ten = 1
for s in S[::-1]:
mod += (int(s) * ten) % 2019
mod %= 2019
M.append(mod)
ten *= 10
ten %= 2019
count = collections.Counter(M)
print(sum([c*(c-1)//2 for c in count.values()]))
For example, if there is a number 1234567, this process calculates the surplus of 7, 67, 567, 4567, 34567, 234567, and 1234567, and the surplus matches. If there is a number of digits, the section is divisible.
In the actual processing, the calculation time is saved by dividing it frequently and performing the surplus calculation.
For a detailed mathematical explanation, see Question E in Article I wrote earlier.
The problem is to find the shortest route from station 1 to all stations. However, you will need silver coins to use the train, and you will have to spend different times at each station to exchange money.
Until now, ABC has only come up to question E, but this is almost the first time for a solid graph problem. I didn't understand at all and gave up.
I saw a lot of explanations and other answers.
First of all, due to the limit of $ 2 \ leq N \ leq 50 $, $ 1 \ leq A_i \ leq 50 $, the total number of silver coins that can be carried in this system is $ 49 \ times50 = 2450 $. (This number can be further reduced depending on the actual value of N, ʻA`, but I will explain with this number for convenience)
Store "minimum time $ T $ when holding coins at station n" in the following array.
T[n][coins]
You can create it as follows. Enter a sufficiently large value as the initial value.
T = [[10**18 for _ in range(2451)] for _ in range(N)]
Possible behavior patterns for each station are "cost cost sheets, time $ t $ to go to adjacent station $ m $" "time $ t $ to use gold coins at the same station" -There is no choice but to exchange for costs (move to $ m = n $ and think that you have consumed negativecosts). Treat this behavior as a tuple.
(m, cost, t)
Save this tuple as an array for each station $ n $.
act[n] = [(Action 1), (Action 2), (Action 3), ....]
The following code is used to store the entered values in these.
N, M, S = map(int, input().split())
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
Since the search is performed from here, the state that is the search source is saved in the priority queue. Treat one state as a tuple. The current time $ currentT $, the current station $ n $, and the number of silver coins in possession $ coins $ are expressed as follows.
(currentT, n, coins)
The initial state of the priority queue is as follows.
que = [(0, 0, S)]
The two-dimensional array T is filled by extracting from this queue in ascending order of t and performing a search. Finally, if you take out the smallest value in T [n], it represents the minimum time to reach station n.
Then, the code written through is as follows.
from heapq import *
N, M, S = map(int, input().split())
T = [[10**18 for _ in range(2451)] for _ in range(N)]
act = [[] for _ in range(N)]
for i in range(M):
U, V, A, B = map(int, input().split())
U -= 1
V -= 1
act[U] += [(V, A, B)]
act[V] += [(U, A, B)]
for i in range(N):
C, D = tuple(map(int, input().split()))
act[i] += [(i, -C, D)]
que = [(0, 0, S)]
while que:
(currentT, n, coins) = heappop(que)
for m, cost, t in act[n]:
#If "at the amount you can pay" "minimum time T"[Destination][Money in possession]Update the value when you can update, and add the state to the queue.
#If the result of exchange exceeds 2450, treat it as 2450 and there is no problem.
if coins >= cost and currentT + t < T[m][min(2450, coins - cost)]:
T[m][min(2450, coins - cost)] = currentT + t
heappush(que, (currentT + t, m, min(2450, coins - cost)))
for i in range(1, N):
print(min(T[i]))
It seems that it is an algorithm called Dijkstra's algorithm. I felt that it was a difficult problem for question E, but I was surprised that the algorithm for the final search part was extremely easy to write.
That's all for this article.
Recommended Posts