[PYTHON] AtCoderBeginnerContest178 Review & Summary (zweite Hälfte)

AtCoder ABC178 Dies ist eine Zusammenfassung der Probleme von AtCoderBeginnerContest178 am 13.09.2020 (So), beginnend mit Problem A, unter Berücksichtigung der Berücksichtigung. Die zweite Hälfte befasst sich mit dem DE-Problem. Klicken Sie hier für die erste Hälfte Das Problem wird zitiert, aber bitte überprüfen Sie die Wettbewerbsseite für Details. Klicken Sie hier für die Wettbewerbsseite Offizieller Kommentar PDF

D Problem Umverteilung

Problemstellung Gegeben die ganze Zahl $ S $. Finden Sie heraus, wie viele Sequenzen es gibt, in denen alle Begriffe Ganzzahlen größer oder gleich $ 3 $ sind und deren Summe $ S $ ist. Die Antwort kann jedoch sehr groß sein. Drucken Sie den Rest geteilt durch $ 10 ^ 9 + 7 $.

Ich hatte es schwer. Wenn $ a_n $ die Antwort ist, wenn $ S = n $, gilt die folgende Graduierungsformel, sodass die Antwort erhalten werden kann, indem die Graduierungsformel der Reihe nach berechnet wird. 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

Problemstellung Auf der zweidimensionalen Ebene befinden sich $ N $ Punkte, und die Koordinaten des $ i $ -ten Punkts sind $ (x_i, y_i) . Es können mehrere Punkte an denselben Koordinaten vorhanden sein. Was ist der maximal mögliche Manhattan-Abstand zwischen zwei verschiedenen Punkten? Allerdings zwei Punkte(x_i,y_i)Wann(x_j,y_j)Manhattan Entfernung|x_i−x_j|+|y_i−y_j|$のこWannをいいます。

Als ich das Problem zum ersten Mal sah, dachte ich, ich müsste nicht über die inneren Punkte nachdenken, indem ich mehrere Punkte verbinde, aber als ich den ersten Punkt so nah wie möglich auswählen wollte, wurde mir klar, wie ich es lösen kann. Schließlich ist es wichtig, ein Diagramm zu zeichnen.

Von $ x_i + y_i = k_i $ ist der Punkt am nächsten an $ (1,1) $ (der Punkt, an dem $ k_i $ am kleinsten ist) und der Punkt am nächsten an $ (10 ^ 9,10 ^ 9) $ ($) Finden Sie den Punkt, an dem k_i $ maximal ist. Von $ -x_i + y_i = n_i $ ist der Punkt am nächsten an $ (10 ^ 9,1) $ (der Punkt, an dem $ n_i $ am kleinsten ist) und der Punkt am nächsten an $ (1,10 ^ 9) $ ( Finden Sie den Punkt, an dem $ n_i $ das Maximum ist.

Die Manhattan-Entfernung zwischen $ k_ {max} $ und $ k_ {min} $ oder die Manhattan-Entfernung zwischen $ n_ {max} $ und $ n_ {min} $ ist die maximal mögliche Manhattan-Entfernung.

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

Persönlich ist der Quellcode selbst im Vergleich zum üblichen Fragensatz bis zur E-Frage einfach, ist es Mathematik? Ich hatte viele Probleme mit der Verwendung, daher war es meine Lieblingsproblematik.

Vielen Dank, dass Sie die zweite Hälfte bis zum Ende gelesen haben.