ABC188
AtCoder Beginner Contest 188 - AtCoder I answered all the questions correctly. After solving A-E in the first 25 minutes, I got into F and spent about 50 minutes. I got completely impatient during the process and got 6 penalties.
- 1WA, I'll trade you, overlooking the condition "to the one with the lowest score." python
X, Y = map(int, input().split())
if X > Y:
Y, X = X, Y
if X + 3 > Y:
print("Yes")
else:
print("No")
- Repeat multiplying and adding in loops. python
def main():
N = int(input())
AS = list(map(int, input().split()))
BS = list(map(int, input().split()))
ret = 0
for i in range(N):
ret += AS[i] * BS[i]
if ret == 0:
print("Yes")
else:
print("No")
- Make a list of IDs of people who will play the next game, play the tournament N-1 times, and return the IDs of the losing side as the last 2 people get python
def main():
N = int(input())
AS = list(map(int, input().split()))
PS = range(2 ** N)
for _r in range(N - 1):
newPS = []
for i in range(0, len(PS), 2):
if AS[PS[i]] > AS[PS[i + 1]]:
newPS.append(PS[i])
else:
newPS.append(PS[i + 1])
PS = newPS
if AS[PS[0]] > AS[PS[1]]:
print(PS[1] + 1)
else:
print(PS[0] + 1)
- Twitter
"The runner-up is the player who won the opposite block to the one who will win", so the answer is the index of the right half and max and the left half max, whichever is smaller [src https://twitter.com/kyopro_friends/status/ 1348264284417978369]
- I see!
- There is no penalty for joining and leaving Prime, so you can calculate the daily cost and pay C for each day you exceed C.
- I'd like to find the daily cost per day, but it's impossible to add up to 10^5 times and up to 10^9 days to the section
- So RangeAdd is two PointAdd.
- The 10^9 day section is hard to hold in array.
- So we'll do it in the dictionary. python
def main():
N, C = map(int, input().split())
from collections import defaultdict
diff = defaultdict(int)
for _n in range(N):
a, b, c = map(int, input().split())
diff[a] += c
diff[b + 1] -= c
keys = list(sorted(diff))
cost = 0
ret = 0
for i in range(1, len(keys)):
cost += diff[keys[i - 1]]
days = keys[i] - keys[i - 1]
ret += min(cost, C) * days
print(ret)
- Twitter
ABC183Just do the simulation in the explanation of ABC183D src
- I see what you mean about doing coordinate compression, that's certainly a good idea.
- I've heard it mentioned under various names, such as Imosu Act (fifth highest of the eight hereditary titles, later demoted to sixth highest of eight) and event sort, but I've never heard the term "event sort" before. I have never heard of event sorting before, but I guess it means "sorting the beginning and ending events of an interval together". I used the "time -> increase/decrease" dictionary, but I guess it means using a list of "(time, increase/decrease)". Might be a bit of a hassle since some of the events are at the same time.
- I'd like to know the likelihood of getting from each vertex to each vertex, but if I do it naively, I'll never get there in time.
- Special Constraints] that "Xi<Yi is guaranteed" is the key.
- In other words, we can update the "minimum purchase cost at the apex that can get there" in the order of decreasing i python
def main():
N, M = map(int, input().split())
AS = list(map(int, input().split()))
from collections import defaultdict
edges = defaultdict(list)
for _i in range(M):
frm, to = map(int, input().split())
edges[frm - 1].append(to - 1) # -1 for 1-origin vertexes
INF = 9223372036854775807
minBuyCost = [INF] * N
ret = -INF
for i in range(N):
ret = max(ret, AS[i] - minBuyCost[i])
m = min(minBuyCost[i], AS[i])
for j in edges[i]:
minBuyCost[j] = min(minBuyCost[j], m)
print(ret)
- Never -1 after +1
- Never +1 after +1, because /2,+1 is cheaper than +1,+1,/2
- Foreshadowing: There is a mistake here.
- If Y is less than X, it can only be +1.
- Put them in a prioritized queue and try them from lowest cost to highest cost.
- I observed that the queue had the same value over and over, so I combined the dictionaries heapq+dict.
- 12WA
- After a while of dawdling, implement the naive solution method and observe discrepancies in a range of small values. python
def blute(X, Y):
queue = {X}
ret = 0
while True:
newqueue = set()
if Y in queue:
return ret
ret += 1
for x in queue:
newqueue.add(x * 2)
newqueue.add(x + 1)
newqueue.add(x - 1)
queue = newqueue
def fulltest():
for x in range(20):
for y in range(20):
s = solve(x, y)
b = blute(x, y)
if s != b:
print(x, y, s, b)
- Cause of error: "A sequence of +1s and -1s is missing the shortest path case."
- In (1) of the following code
- The statement "never +1 after +1" is incorrect.
- No /2 would come after that, but it could have gone straight to the finish line.
python
def solve(X, Y):
from heapq import heappush, heappop
queue = [(0, Y)]
minCost = {Y: 0}
INF = 9223372036854775807
def add(cost, y):
c = minCost.get(y, INF)
if cost < c:
minCost[y] = cost
heappush(queue, (cost, y))
while True:
cost, y = heappop(queue)
if y == X:
return cost
if y < X:
add(cost + (X - y), X)
continue
if y == X + 1:
add(cost + 1, X)
continue
add(cost + (y - X), X) # (1)
if y % 2 == 0:
add(cost + 1, y // 2)
else:
add(cost + 2, (y + 1) // 2)
add(cost + 2, (y - 1) // 2)
This page is auto-translated from /nishio/ABC188 using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.