ABC170
I solved three atcoder problems, looked at E because I had no idea how to solve D's timeout, and read the explanation of Third Algorithm Practical Skills Test because I couldn't think of a data structure that satisfied E's requirements (I thought the solution for problem K might be helpful, but it was a bit simpler than my method, so it wasn't). (I thought the solution to problem K might be helpful, but it was a simpler version of the method I used, so it was not helpful.) https://gyazo.com/b9887311c157ca03d7ab1ac36fc195b8
The explanation PDF says that C is an easy problem and I don't have anything to write about it either. The rate doesn't go up much.
https://gyazo.com/e048a756ae5b81dfe1171edb62cc5d59
Problem D
The question is to answer how many numbers are "not divisible by everything but themselves" given 200,000 numbers.
A straightforward division is TLE on the order of 200,000 squared.
I could think of a few minor branch cuts, but could not come up with a way to radically change the order.
The range of values is less than 10^6, so the maximum table should be that size.
Create tables up to the maximum value, in order from largest to smallest.
Write one in your place.
Write 0 at your multiple.
Do the "Write 0 in multiples". If it is divisible by a number other than itself, then the number less than itself should be overwritten when you do "write 0 in the multiples".
Finally, adding all the numbers written in the table gives the number of numbers that satisfy the condition.
However, there is a trap. When the same number appears more than once, this method will cause a 1 to stand for that number. So if it is the second time or later, you need to write 0.
code:python
N = int(input())
AS.sort(reverse=True)
table = 0 * (MAX_AS + 1) # 1..max(AS) alreadyVisited = {}
for i in range(N):
if alreadyVisited.get(x, False):
continue
while True:
x += dx
if x > MAX_AS:
break
print(sum(table))
---
This page is auto-translated from /nishio/ABC170. 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.