ABC188

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.

https://gyazo.com/c4d11f9ce3d61e26fe505cf52f0fcaeb

https://gyazo.com/4609564a3c452f696c5c8b8ae80f176e

https://gyazo.com/9440dcf0419562d1b705b2004be36511

1WA, I'll trade you, overlooking the condition "to the one with the lowest score."

code:python

X, Y = map(int, input().split())

if X > Y:

Y, X = X, Y

if X + 3 > Y:

print("Yes")

else:

print("No")

https://gyazo.com/d780c78a7d0081ce919dd80c915291da

Repeat multiplying and adding in loops.

code: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):

if ret == 0:

print("Yes")

else:

print("No")

https://gyazo.com/0b911fc8e109fee21c9c592e6e26e671

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

code: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):

else:

PS = newPS

else:

Twitter

I see!

https://gyazo.com/9e383b268bf227d379e4cef649a273e1

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

The 10^9 day section is hard to hold in array.

So we'll do it in the dictionary.

code: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())

keys = list(sorted(diff))

cost = 0

ret = 0

for i in range(1, len(keys)):

ret += min(cost, C) * days

print(ret)

Twitter

https://gyazo.com/643399598cd75f589f09039a4773f7d8

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

code: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())

INF = 9223372036854775807

ret = -INF

for i in range(N):

print(ret)

https://gyazo.com/2f312cac88ff2f3803637e6be88c1ff5

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.

12WA

After a while of dawdling, implement the naive solution method and observe discrepancies in a range of small values.

code: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.

code:python

def solve(X, Y):

from heapq import heappush, heappop

minCost = {Y: 0}

INF = 9223372036854775807

def add(cost, y):

c = minCost.get(y, INF)

if cost < c:

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)

Twitter

---