Atcoder Acing Programming Contest Python

Summary

It was difficult. It was A, B, C 3 questions AC. I don't know the binary number well, so D skips the moment I see the problem, and I feel like I can do the E problem, but I don't understand even if I look at the answer example.

problem

(https://atcoder.jp/contests/aising2020/tasks)

A. Number of Multiples

Answer

L, R, d = map(int, input().split())

count = 0
for i in range(L, R+1):
    if i % d == 0:
        count += 1

print(count)

I wrote it obediently. Others seem to be writing in a cooler way.

B. An Odd Problem

Answer

N = int(input())
a = list(map(int, input().split()))

count = 0
for i in range(0, N, 2):
    if i % 2 == 0 and a[i] % 2 != 0:
        count += 1
print(count)

I wrote this honestly as well. The problem is odd, but the subscripts in the list are even.

C. XYZ Triplets

Answer

N = int(input())

keys = [i for i in range(1, N+1)]
values = [0] * N
count_dict = dict(zip(keys, values))

for x in range(1, N//6+7):
    for y in range(x, N//6+7):
        for z in range(y, N//6+7):
            n = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if n > N:
                break
            if x == y and y == z:
                count_dict[n] += 1
            elif x != y and x != z and y != z:
                count_dict[n] += 6
            else:
                count_dict[n] += 3

for v in count_dict.values():
    print(v)

To be honest, turn the for loop of `range (1, N + 1) ``` for each of x, y, z and `x ** 2 + y ** 2 + z ** 2 + x It seems that * y + y * z + z * x = n``` should be judged. However, since the constraint is 10 ** 4, it will not be in time for a normal triple loop, so consider reducing the amount of calculation.

The first thing I thought about was that if `(x, y, z) = (1,1,1) ```, n is 6, so the maximum value to turn in a for loop is . N // 6 ``` looks good. However, considering that the subscript must be ``` + 1```, I chose `` N // 6 + 7 with a margin. (In production, I used `` `N // 6 + 7, but if I use the constraint 10 ** 4 in reverse, `(x, y, z)` You can see that can only be used up to about 100. I didn't notice this during production ...)

So, it seems that this alone will probably not be in time, so I will consider reducing the amount of calculation a little more.

If you give some examples, you will notice the following. --(1,2,3) `` `and` `(1,3,2)` `` and `` `(2,1,3)` `` and` `(2,3) , 1) and (3,1,2)`` and ``(3,2,1) , where x, y, z are all different, n is equivalent There are 6 combinations that become --The two are the same, like ``` (1,1,2)`` and ``(1,2,1) `` and (2,1,1) There are three combinations where n is equivalent when one is different --There is one combination where n is equivalent if all the numbers are the same, such as ``(1,1,1)` ``.

Therefore, the range of the for loop of x, y, z is `range (1, N // 6 + 7)`, `range (x, N // 6 + 7)`, respectively. As `range (y, N // 6 + 7)`, it seems that count should be +6, +3, +1 in the above three cases.

After that, if n exceeds N, you can manage to make it by adding `` `break```.