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.)

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.

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.

Solution. Eratosthenes’ sieve. 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.

python

N = int(input())
AS = [int(x) for x in input().split()]

AS.sort(reverse=True)
MAX_AS = AS[0]
table = [0] * (MAX_AS + 1)  # 1..max(AS)

alreadyVisited = {}
for i in range(N):
    x = dx = AS[i]
    if alreadyVisited.get(x, False):
        table[x] = 0
        continue
    alreadyVisited[x] = True

    table[x] = 1
    while True:
        x += dx
        if x > MAX_AS:
            break
        table[x] = 0

print(sum(table))

ABC170_E

This page is auto-translated from /nishio/ABC170 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.