ABC183

Finally, I got all the questions right! And no mistakes.

It was the first time I had ever finished all the questions during a contest, so I was washing dishes and the bathtub because I didn't know what to do with the 21 minutes or so of time I had left (lol).

https://gyazo.com/c3a83f04dc6802c2d35d8b209448675b

F was not intended to be a correct answer, but rather "I think it's no good, but let's check if the speed is the only problem and not the answer," and I was surprised that it was sent within a surprisingly short period of time. In other words, the consideration was wrong, but the mistake was "estimating the speed slower than it actually is," so I submitted the wrong answer and it was accepted.

A

Some people thought of max(0, x) or something, but I did it naively. 40sec

code:python

x = int(input())

if x > 0:

print(x)

else:

print(0)

B

I was surprised that the billiard ball had a radius of zero.

I thought I didn't get my best math problem this time, but it seems some people melted 30 minutes or did a bifurcated search on this problem.

I thought a little worried about what happens when dx is negative, but don't worry about it 5min

Official Explanation

Endogenize the change from Sx to Gx to Sy:Gy

$ \frac{S_x G_y+G_x S_y}{S_y+G_y}

My solution

$ \frac{S_y (G_x - S_x)}{G_y + S_y} + S_x

code:python

SX, SY, GX, GY = map(int, input().split())

dx = GX - SX

dy = GY + SY

ret = SY / dy * dx + SX

print(ret)

C

The factorial of 8 is 40320.

All searches are OK.

code:python

def solve(N, K, dist):

from itertools import permutations

ret = 0

for order in permutations(range(1, N)):

d = 0

prev = 0

for x in order:

prev = x

if d == K:

ret += 1

return ret

D

Note that it cannot be stored.

Since it cannot be stored, it is necessary to find out the amount of demand at each point in time and not to exceed the supply

code:python

N, W = map(int, input().split())

for _i in range(N):

S, T, P = map(int, input().split())

usage = 0

for v in diff:

usage += v

if usage > W:

print("No")

return

print("Yes")

E

Thoughts.

A normal DP would be 2000x2000x3000x2000, which is not going to make it.

If the range sum in the three directions is made constant order using the cumulative sum, it looks good because it's 2000 x 2000.

Like this

code:python

# hvalue = 0

# p = pos

# while True:

# p -= 1

# break

# debug(divmod(pos, WIDTH), hvalue, msg=":pos")

# debug(divmod(pos, WIDTH), hvalue, msg=":accum")

Deals with cumulative sums in three directions: horizontal, vertical, and diagonal.

What you can't do through the wall, you can do by setting the cumulative sum to zero at the wall.

code:python

def solve(H, W, data):

MOD = 1_000_000_007

N = len(data)

for pos in allPosition():

if pos == WIDTH + 1:

continue

continue

ret = h_value + v_value + d_value

ret %= MOD

return ret

F

Thoughts.

There are 200,000 possible class types.

Doesn't look like it can be done with UnionFind?

Can you do it in logarithmic order?

When using UnionFind, have the representative source have the number of items for each class.

If we naively have an array of values for "how many people are in class x," then O(N)

Readout is in constant order

I can drop this down to logarithmic order, so I want to speed up the merge instead.

Set the readout to logarithmic order → binary search

What if we have it as a sorted array?

Merging is linear order of content quantity

If you just want to order the contents, a hash table is fine.

Defaultdict because there may be no key, or no, it's a piece count, so Counter.

Let's try sending with it once and see if there are any other bugs -> AC surprisingly easily.

mounting

Modify the UnionFind library to update Counter at merge time

code:python

def unite(x, y):

x = find_root(x)

y = find_root(y)

if x == y:

return # already united

else:

body (of a machine)

code:python

def main():

global cls

from collections import Counter

N, Q = map(int, input().split())

init_unionfind(N)

CS = list(map(int, input().split()))

for _q in range(Q):

typ, a, b = map(int, input().split())

if typ == 1:

unite(a - 1, b - 1)

else:

root = find_root(a - 1)

Official Explanation

If you merge the smaller one into the larger one, the size will more than double with each merge, so at worst it will be merged only logN times, so it will be less than NlogN

This estimate was not made.

I knew it was a worst case scenario and I knew it wasn't working, but I hadn't come up with a solution.

However, the UnionFind implementation "merges the lower ranks into the higher ranks" to compress the height of the tree, thereby causing a similar effect, but in time.

---