** 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

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

Total number of submissions: 5748

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 |

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 % |

- Display rate, ash does not include first-time participants </ font>

- 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 are not in ascending order **

### Results of me (Unidayo) (reference)

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_i Absolute 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_i Absolute 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

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 $ **

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