PAST2M
https://gyazo.com/b74deda81b8400cfd3e8c683aff07100
PAST2M
Thoughts.
0 when the favorite dish is 0.
Otherwise, the pattern will be Period D, starting with the timing of your favorite dish.
Divide L by D.
But if I calculate the pattern of period D for each of the N employees, 10^10 will not make it, what should I do?
Official Explanation
https://gyazo.com/c60e3ee7a911c22c643bb530acf812c6
A new thought.
L is constant regardless of employees
If I know the next day the same favorite menu item is served, I know how many times I'll eat a menu item I don't like in between.
Tj varies from person to person, 10^9
Requires processing on the order of less than linear
Doubling to logarithmic order
The problem of finding x when f(x) = y by doubling the sum f(x) of the number of times you ate your favorite dish x times.
mounting
The specification is complex, so for the sake of clarity, I implemented it naively first
sample AC:
code:python
def solve(D, L, N, CS, KFTS):
for K, F, T in KFTS:
F -= 1 # 1-origin to 0-origin
ret = 0
ret = 1
countdown = T - 1
cur = F
prev = cur
while countdown:
cur += 1
ret += 1
prev = cur
countdown -= 1
elif cur - prev == L:
prev = cur
countdown -= 1
print(ret)
I didn't take the extra and forgot that RE and F are 1-origin and did WA and so on.
The problem is that this while countdown is 10^9.
The commentary dubbed it one step to the next favorite dish, but if you're going to dub it anyway, why not just one step per day?
No, because if you don't use your favorite dish as a starting point, you won't be able to determine how many dishes you don't like to eat.
A version that records the location of the "next same dish" in advance and skips ahead once a favorite dish is found.
code:python
def solve(D, L, N, CS, KFTS):
MAX_C = 10 ** 5
for i, d in enumerate(CS):
d -= 1 # to 0-origin
else:
for d in range(MAX_C):
for K, F, T in KFTS:
F -= 1 # 1-origin to 0-origin
ret = 0
ret = 1
countdown = T - 1
cur = F
prev = cur
while countdown:
cur += 1
ret += 1
countdown -= 1
while True:
d = n - cur
if d < 0:
d += D
up = (d - 1) // L + 1
if countdown >= up:
countdown -= up
cur = n
ret += 1
continue
else:
countdown = 0
break
elif cur - prev == L:
prev = cur
countdown -= 1
print(ret)
Next, we'll dub this "moving on" section.
Scope.
Worst case scenario, if the next plate is next to it, the number of dishes is only +1, so it takes 10^9 times to get to 10^9.
2^30 would certainly be over, [0, 30) is OK.
Pre-calculation of up diff This is one step
doubling
I didn't realize I needed the value of next for doubling ups, and I implemented it wrong once.
code:python
# doubling
for _i in range(1, 30):
new_next = []
new_ups = []
for i in range(D):
new_next.append(n2)
new_ups.append(u1 + u2)
db_next.append(new_next)
db_ups.append(new_ups)
code:python
for i in range(30 - 1, -1, -1):
if countdown >= up:
countdown -= up
ret += 2 ** i
You're still going to TLE on this one, right? (19 TLE to 10 TLE)
Oh, right, people who don't have a favorite dish will run 10^9.
code:python
print(0)
continue
Still, 4TLE.
It's not good that you're asking for a loop of "the first day your preferred dish appears after F."
Let's bifurcate this one, too.
---
This page is auto-translated from /nishio/PAST2M. 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.