[PYTHON] AtCoderBeginnerContest178 Review & Summary (second half)

AtCoder ABC178 This is a summary of the AtCoder Beginner Contest 178 problems that took place on 2020-09-13 (Sun), starting with problem A and taking into account the considerations. The second half deals with the DE problem. Click here for the first half The problem is quoted, but please check the contest page for details. Click here for the contest page Official commentary PDF

D problem Redistribution

Problem statement The integer $ S $ is given. Find out how many sequences there are in which all terms are integers greater than or equal to $ 3 $ and their sum is $ S $. However, the answer can be very large, so print the remainder divided by $ 10 ^ 9 + 7 $.

I had a hard time. If $ a_n $ is the answer when $ S = n $, the following recurrence formula holds, so the answer can be obtained by calculating the recurrence formula in order. a_n = a_{n-3} + a_{n-1}

abc178d.py

s = int(input())
mod = 10**9 + 7
a_list = [0] * (2000 + 1)
a_list[0] = 1
a_list[1] = 0
a_list[2] = 0
a_list[3] = 1
for i in range(4, s + 1):
    a_list[i] = a_list[i - 1] + a_list[i - 3]
    a_list[i] %= mod
print(a_list[s])

E problem Dist Max

Problem statement There are $ N $ points on the 2D plane, and the coordinates of the $ i $ th point are $ (x_i, y_i) . There can be multiple points at the same coordinates. What is the maximum possible Manhattan distance between two different points? However, two points(x_i,y_i)When(x_j,y_j)Manhattan distance|x_i−x_j|+|y_i−y_j|$のこWhenをいいます。

When I first saw the problem, I thought that I wouldn't have to think about the inner points by connecting several points, but when I wanted to make the first point to be selected as close as possible, I realized how to solve it. After all it is important to draw a diagram.

From $ x_i + y_i = k_i $, the point closest to $ (1,1) $ (the point where $ k_i $ is the smallest) and the point closest to $ (10 ^ 9,10 ^ 9) $ ($) Find the point where k_i $ is maximum). From $ -x_i + y_i = n_i $, the point closest to $ (10 ^ 9,1) $ (the point where $ n_i $ is the smallest) and the point closest to $ (1,10 ^ 9) $ ( Find the point where $ n_i $ is the maximum).

The Manhattan distance of $ k_ {max} $ and $ k_ {min} $ or the Manhattan distance of $ n_ {max} $ and $ n_ {min} $ is the maximum possible Manhattan distance.

abc178e.py

n = int(input())
point_dict1 = {}
point_dict2 = {}
for i in range(n):
    x, y = map(int, input().split())
    point_dict1[x + y] = (x, y)
    point_dict2[y - x] = (x, y)
min_point1 = min(point_dict1)
max_point1 = max(point_dict1)
min_point2 = min(point_dict2)
max_point2 = max(point_dict2)
print(max(max_point1 - min_point1, max_point2 - min_point2))

Personally, compared to the usual question set, the source code itself is simple up to the E question, math? I had a lot of problems using, so it was my favorite problem set.

Thank you for reading the second half to the end.