[AtCoder explanation] Control ABC180 A, B, C problems with Python!

** A, B, C problems ** of ** AtCoder Beginner Contest 180 ** will be explained as carefully as possible with ** Python3 **.

I am aiming to explain a solution that satisfies the following three points, not just a method that can be solved.

--Simple: You don't have to think about anything extra --Easy to implement: I'm glad that mistakes and bugs are reduced ――It doesn't take long: The performance goes up and you have more time left for later problems.

If you have any questions or suggestions, please leave a comment or Twitter. Twitter: u2dayo

table of contents

[ABC180 Summary](# abc180-Summary) [A problem "box"](#a problem box) [B problem "Various distances"](#b problem variable-distances) [C problem "Cream puff"](#c problem cream-puff)

ABC180 Summary

Total number of submissions: 5748

performance

Performance AC Score time Ranking(Within Rated)
200 A-C--- 400 Half an hour 4393(4250)Rank
400 ABC--- 600 51 minutes 3638(3499)Rank
600 ABC--- 600 23 minutes 3008(2869)Rank
800 ABCD-- 1000 115 minutes 2357(2219)Rank
1000 ABCD-- 1000 62 minutes 1749(1614)Rank
1200 ABCD-- 1000 23 minutes 1241(1110)Rank
1400 ABCDE- 1500 85 minutes 850(724)Rank
1600 ABCDE- 1500 60 minutes 565(441)Rank
1800 ABCDE- 1500 44 minutes 364(251)Rank
2000 ABCDE- 1500 33 minutes 227(131)Rank
2200 ABCDE- 1500 26 minutes 136(63)Rank
2400 ABCDE- 1500 17 minutes 83(29)Rank

Correct answer rate by color

color Number of people A B C D E F
Ash 2412 99.0 % 68.4 % 64.4 % 12.4 % 1.2 % 0.0 %
tea 1093 99.5 % 92.5 % 93.7 % 45.6 % 7.0 % 0.2 %
Green 889 99.9 % 97.6 % 99.0 % 79.0 % 31.6 % 0.1 %
water 544 100.0 % 99.8 % 99.8 % 95.8 % 73.2 % 0.7 %
Blue 268 100.0 % 99.6 % 99.6 % 97.8 % 94.0 % 6.3 %
yellow 109 98.2 % 97.2 % 99.1 % 98.2 % 91.7 % 26.6 %
orange 26 100.0 % 100.0 % 100.0 % 96.2 % 96.2 % 69.2 %
Red 8 62.5 % 62.5 % 62.5 % 62.5 % 75.0 % 100.0 %

Brief commentary

A problem (5699 people AC) "box"
It's OK if you write the code for addition and subtraction.
B problem (4683 people AC) "Various distances" You can use the
for loop to find it exactly as it is written.
C problem (4585 people AC) "Cream puff"
This is a problem to output divisors in ascending order. Divisor enumeration can be done with $ O (N) $.
D problem (2471 AC) "Takahashi Unevolved" [Not explained in this article] While it is better to double
$ A $, actually multiply by $ A $ to simulate. When it is better to add $ B $, calculate and calculate the number of remaining times. From $ 2 ^ {60}> 10 ^ {18} $, the number of times to multiply $ A $ is at most $ 60 $.
E problem (1189 people AC) "Traveling Salesman among Aerial Cities" [Not explained in this article]
The cost between cities is only $ 17 ^ 2 = 375 $ at most, and it is easy to find, so find it first. Then, it becomes just a traveling salesman problem. The traveling salesman problem is $ O (N!) $ When trying all routes, but $ O (N ^ {2} 2 ^ {N}) $ using the so-called ** bitDP ** dynamic programming method. Can be solved with.
F problem (80 people AC) "Unbranched" [not explained in this article]
It seems to be dynamic programming. As the problem name suggests, the graph does not branch.

Results of me (Unidayo) (reference)

screenshot.266.png

Since I was studying applied information, it is a virtual participation.

A problem "box"

** Problem page **: A --box

Consideration

You don't have to think about the case where trying to retrieve $ A $ is not enough. This is because it is not written in the problem statement and the constraint is $ A \ le {100} \ le {N} $.

Therefore, $ N-A + B $ is the answer.

code

N, A, B = map(int, input().split())
print(N - A + B)

Problem B "Various distances"

** Problem page **: B --Various distances

Consideration

The formula for finding the distance is written in the problem statement. Even if you don't understand the meaning of the distance, you can calculate it exactly as it is written. (By the way, it is impossible to think concretely about the distance beyond the $ 4 $ dimension.)

The meaning of each formula is as follows.

1. Manhattan distance

γ€Ž x_iAbsolute value of|x_i|] Is the sum (total).

2. Euclidean distance

The square root of the sum of "$ x_i $ squared $ {x_i} ^ {2} $". If you square a negative value, it will be positive, so you can remove the absolute value.

It may seem difficult at first glance, but it will be $ \ sqrt {x ^ 2 + y ^ 2} $ in the $ 2 $ dimensional plane and $ \ sqrt {x ^ 2 + y ^ 2 + z ^ 2} $ in the $ 3 $ dimensional space. .. This is a normal distance to learn in middle school or high school math.

3. Chebyshev distance

γ€Žx_iAbsolute value of|x_i|] Is the maximum value.

Implementation

Create variables first, second_temp, third with an initial value of $ 0 $. It corresponds to "Manhattan distance", "Euclidean distance square root contents", and "Chebyshev distance" in the order of output.

Look at the elements of the list of point coordinates X in a for loop, $ 1 $ each, and calculate these $ 3 $.

Processing in the for loop

This is the process performed in the for loop.

The $ 1 $ th "Manhattan distance" is first + = abs (x) because you can add the absolute values.

The $ 2 $ th "contents of the square root of the Euclidean distance" is second_temp + = x ** 2 because you only need to add the square.

The $ 3 $ th "Chebyshev distance" is third = max (third, abs (x)) because the maximum absolute value can be updated.

Post-loop processing

Take the second route to find the" Euclidean distance ". That is, second = second_temp ** 0.5.

Since all were requested, output in the order of first, second, third, and the end.

code

You don't have to worry about it in Python, but second_temp can be as big as $ 10 ^ {15} $. In C ++ etc., you need to be careful about overflow.

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

first, second_temp, third = 0, 0, 0

for x in X:
    first += abs(x)
    second_temp += x ** 2
    third = max(third, abs(x))

second = second_temp ** 0.5

print(first)
print(second)
print(third)

bonus

You don't have to do that, but you can also use the higher-order functions (functions that take a function as arguments) map and reduce to find each in a $ 1 $ line.

#Maybe there is a better way to write
N = int(input())
X = list(map(int, input().split()))

print(sum(map(abs, X)))
print((sum(map(lambda x: x ** 2, X))) ** 0.5)
print(max(map(abs, X)))

C problem "Cream puff"

** Problem page **: C --Cream puff

Meaning of the problem

Output the divisors of $ N $ in ascending order.

Consideration

Cream puffs can cost up to $ 10 ^ {12} $, so trying everything from $ 1 $ to $ 10 ^ {12} $ is not enough.

By the way, ** "the number of people who can divide cream puffs equally without dividing them" ** means ** "the number divisible by $ N $" **.

** A number that is divisible by an integer $ N $ ** is called a ** divisor of $ N $ **.

** You can enumerate divisors with $ O (\ sqrt {N}) $. ** $ \ sqrt {10 ^ {12}} = 10 ^ 6 , so it's in time. ( 10 ^ 6 $ is $ 100 $ million)

Efficient divisor enumeration method

abc180_c.png

The divisors have the property of ** "If you know all the divisors below $ \ sqrt {N} $, you can divide $ N $ by them to find all the divisors above $ \ sqrt {N} $" **. there is.

Taking advantage of this property, ** "Try dividing $ N $ by $ \ sqrt {N} $, and if it is divisible, add $ x $ and $ N / x $ to the divisor list" ** , $ O (\ sqrt {N}) $ can be used to enumerate divisors.

Detailed reason
Suppose $ N $ has a divisor of $ x $. At this time, $ \ frac {N} {x} $ is always a divisor of $ N $.

That's because $ N \ div {\ frac {N} {x}} = N \ times {\ frac {x} {N}} = x $. For example, $ 36 = 3 \ times {12} $ is a divisor of both $ 3 $ and $ 12 $.

We will call such $ x $ and $ \ frac {N} {x} $ ** "divisor pairs" **. ** A "divisor pair" is always less than or equal to $ \ sqrt {N} $ and the other is greater than or equal to $ \ sqrt {N} $. ** **

If there is a divisor greater than or equal to ** $ \ sqrt {N} $, then the pair is always less than or equal to $ \ sqrt {N} $. Therefore, you can enumerate the divisors by dividing $ N $ by all the divisors below $ \ sqrt {N} $. ** **

Proof
A "divisor pair" always proves that one is less than $ \ sqrt {N} $ and the other is more than $ \ sqrt {N} $.

Both are smaller than $ \ sqrt {N} $, that is, $ x \ lt {\ sqrt {N}} $ and $ \ frac {N} {x} \ lt {\ sqrt {N}} $.

Multiplying the inequalities

x\times{\frac{N}{x}} < \sqrt{N}\times{\sqrt{N}}\\
N < N

Will be. This is strange because $ N = N $. In other words, the assumption cannot be wrong.

Similarly, there can be no "both greater than $ \ sqrt {N} $" in the opposite direction of the inequality.

From the above, one of the "divisor pairs" is always $ \ sqrt {N} $ or less, and the other is $ \ sqrt {N} $ or more.

Implementation

Basically, all you have to do is write the code below.

divs = []

x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.append(x)
        divs.append(N // x)
    x += 1

However, there are $ 2 $ problems with this code.

-** When $ \ sqrt {N} $ becomes a divisor, $ \ sqrt {N} $ is added to the list by $ 2 $ **

  1. ** Results are not in ascending order **

The $ 1 $ second problem can be solved by dividing the case where $ \ sqrt {N} $ is a divisor, but it is troublesome.

We will use ** set type ** to avoid duplication. The set type handles "unordered sets" and contains only $ 1 $ of the same element. If you add an element that already exists, nothing happens.

The $ 2 $ problem can be solved by sorting. However, the set type does not have the concept of order and cannot be sorted. Convert to a list and then sort.

code

N = int(input())
divs = set()  #Use set to avoid duplication

#Mathematically x<= N ** 0.Same as 5, but safer to compare with an error-free integer
x = 1
while x ** 2 <= N:
    if N % x == 0:
        divs.add(x)  #Add to set is add, not append
        divs.add(N // x)
    x += 1

ans = list(divs)  #I want to sort in ascending order, so make a list and sort
ans.sort()

for x in ans:
    print(x)

Recommended Posts