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).
A
- Some people thought of max(0, x) or something, but I did it naively. 40sec 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
- My solution
- python
- Endogenize the change from Sx to Gx to Sy:Gy
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. 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:
d += dist[prev][x]
prev = x
d += dist[prev][0]
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
- I tried to sort the list by start and end, but I thought it would be too much trouble to implement it properly without getting bugs when the start and end overlap at the same point, so I looked at the problem condition again and found that the time resolution was about 10^5 Imosu Act (fifth highest of the eight hereditary titles, later demoted to sixth highest of the eight). hereditary titles, later demoted to sixth highest of eight)]. python
N, W = map(int, input().split())
diff = [0] * 20_0010
for _i in range(N):
S, T, P = map(int, input().split())
diff[S] += P
diff[T] -= P
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.
- First make sure the sample case passes with a straightforward DP, then change to a cumulative sum DP with cumulative sum.
- Like this python
# hvalue = 0
# p = pos
# while True:
# p -= 1
# if data[p] == 0:
# break
# hvalue += table[p]
# debug(divmod(pos, WIDTH), hvalue, msg=":pos")
hvalue = h_accum[pos - 1]
# 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.
- I'm [[Put the map in a 1D array]].
python
def solve(H, W, data):
MOD = 1_000_000_007
N = len(data)
table = [0] * N
h_accum = [0] * N
v_accum = [0] * N
d_accum = [0] * N
table[WIDTH + 1] = 1
h_accum[WIDTH + 1] = 1
v_accum[WIDTH + 1] = 1
d_accum[WIDTH + 1] = 1
for pos in allPosition():
if pos == WIDTH + 1:
continue
if data[pos] == 0:
table[pos] = 0
h_accum[pos] = 0
v_accum[pos] = 0
d_accum[pos] = 0
continue
h_value = h_accum[pos - 1]
v_value = v_accum[pos - WIDTH]
d_value = d_accum[pos - WIDTH - 1]
ret = h_value + v_value + d_value
ret %= MOD
table[pos] = ret
h_accum[pos] = (h_accum[pos - 1] + ret) % MOD
v_accum[pos] = (v_accum[pos - WIDTH] + ret) % MOD
d_accum[pos] = (d_accum[pos - WIDTH - 1] + 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 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 python
def unite(x, y):
x = find_root(x)
y = find_root(y)
if x == y:
return # already united
if rank[x] < rank[y]:
parent[x] = y
cls[y].update(cls[x]) # ***
else:
parent[y] = x
if rank[x] == rank[y]:
rank[x] += 1
cls[x].update(cls[y]) # ***
- body (of a machine)
python
def main():
global cls
from collections import Counter
N, Q = map(int, input().split())
init_unionfind(N)
CS = list(map(int, input().split()))
cls = [Counter([CS[i] - 1]) for i in range(N)]
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)
print(cls[root].get(b - 1, 0))
- 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 fit less than NlogN - Move from the smallest to the largest improves the worst-case computational complexity
- 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.
This page is auto-translated from /nishio/ABC183 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.