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.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second half)
AtCoderBeginnerContest161 Review & Summary (second half)
AtCoderBeginnerContest164 Review & Summary (second half)
AtCoderBeginnerContest176 Review & Summary (second half)
AtCoderBeginnerContest168 Review & Summary (second half)
AtCoderBeginnerContest169 Review & Summary (second half)
AtCoderBeginnerContest166 Review & Summary (second half)
AtCoderBeginnerContest171 Review & Summary (second half)
AtCoderBeginnerContest174 Review & Summary (second half)
AtCoderBeginnerContest173 Review & Summary (second half)
AtCoderBeginnerContest177 Review & Summary (second half)
AtCoderBeginnerContest175 Review & Summary (first half)
AtCoderBeginnerContest164 Review & Summary (first half)
AtCoderBeginnerContest169 Review & Summary (first half)
AtCoderBeginnerContest174 Review & Summary (first half)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (first half)
AtCoderBeginnerContest170 Review & Summary (first half)
AtCoderBeginnerContest167 Review & Summary (first half)
AtCoderBeginnerContest177 Review & Summary (first half)
AtCoderBeginnerContest168 Review & Summary (first half)
AtCoderBeginnerContest178 Review & Summary (first half)
AtCoderBeginnerContest171 Review & Summary (first half)
AtCoderBeginnerContest166 Review & Summary (first half)
AtCoderBeginnerContest161 Review & Summary (first half)
AtCoderBeginnerContest172 Review & Summary (first half)
AtCoderBeginnerContest176 Review & Summary (first half)
AtCoderBeginnerContest180 Review & Summary
AtCoderBeginnerContest181 Review & Summary
AtCoderBeginnerContest182 Review & Summary
AtCoderBeginnerContest183 Review & Summary
AtCoderBeginnerContest179 Review & Summary
Django Girls Tutorial Summary First Half