AtCoderBeginnerContest178 Review & Summary (second semestre)

AtCoder ABC178 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 178 qui a eu lieu le 13/09/2020 (dimanche), en commençant par le problème A et en tenant compte des considérations. La seconde partie traite du problème de l'ED. Cliquez ici pour la première moitié Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF

D problème Redistribution

Énoncé du problème Compte tenu de l'entier $ S $. Découvrez combien de séquences il y a dans lesquelles tous les termes sont des entiers supérieurs ou égaux à $ 3 $ et leur somme est $ S $. Cependant, la réponse peut être très volumineuse, alors imprimez le reste divisé par 10 $ ^ 9 + 7 $.

J'ai eu du mal. Si $ a_n $ est la réponse lorsque $ S = n $, la formule graduelle suivante est valable, donc la réponse peut être obtenue en calculant la formule graduelle dans l'ordre. 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 problème Dist Max

Énoncé du problème Il y a $ N $ points sur le plan bidimensionnel, et les coordonnées du $ i $ th point sont $ (x_i, y_i) . Il peut y avoir plusieurs points aux mêmes coordonnées. Quelle est la distance maximale possible à Manhattan entre deux points différents? Cependant, deux points(x_i,y_i)Quand(x_j,y_j)Distance de Manhattan|x_i−x_j|+|y_i−y_j|$のこQuandをいいます。

Quand j'ai vu le problème pour la première fois, j'ai pensé que je n'aurais pas à penser aux points intérieurs en reliant plusieurs points, mais quand j'ai voulu faire en sorte que le premier point soit sélectionné le plus près possible, j'ai réalisé comment le résoudre. Après tout, il est important de dessiner un diagramme.

De $ x_i + y_i = k_i $, le point le plus proche de $ (1,1) $ (le point où $ k_i $ est le plus petit) et le point le plus proche de $ (10 ^ 9,10 ^ 9) $ ($) Trouvez le point où k_i $ est maximum). De $ -x_i + y_i = n_i $, le point le plus proche de $ (10 ^ 9,1) $ (le point où $ n_i $ est le plus petit) et le point le plus proche de $ (1,10 ^ 9) $ ( Trouvez le point où $ n_i $ est le maximum).

La distance de Manhattan entre $ k_ {max} $ et $ k_ {min} $ ou la distance de Manhattan entre $ n_ {max} $ et $ n_ {min} $ est la distance maximale possible de Manhattan.

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

Personnellement, comparé à l'ensemble de questions habituel, le code source lui-même est simple jusqu'à la question E, est-ce des mathématiques? J'ai eu beaucoup de problèmes d'utilisation, c'était donc mon ensemble de problèmes préféré.

Merci d'avoir lu la seconde moitié jusqu'à la fin.

Recommended Posts

AtCoderBeginnerContest178 Review & Summary (second semestre)
AtCoderBeginnerContest161 Review & Summary (second semestre)
AtCoderBeginnerContest164 Review & Summary (second semestre)
AtCoderBeginnerContest176 Review & Summary (second semestre)
AtCoderBeginnerContest168 Review & Summary (second semestre)
AtCoderBeginnerContest169 Review & Summary (second semestre)
AtCoderBeginnerContest166 Review & Summary (second semestre)
AtCoderBeginnerContest171 Review & Summary (second semestre)
AtCoderBeginnerContest174 Review & Summary (second semestre)
AtCoderBeginnerContest173 Review & Summary (second semestre)
AtCoderBeginnerContest177 Review & Summary (second semestre)
AtCoderBeginnerContest175 Review & Summary (premier semestre)
AtCoderBeginnerContest164 Review & Summary (premier semestre)
AtCoderBeginnerContest169 Review & Summary (premier semestre)
AtCoderBeginnerContest174 Review & Summary (premier semestre)
AtCoderBeginnerContest173 Review & Summary (First Half)
AtCoderBeginnerContest165 Review & Summary (premier semestre)
AtCoderBeginnerContest170 Review & Summary (premier semestre)
AtCoderBeginnerContest167 Review & Summary (premier semestre)
AtCoderBeginnerContest177 Review & Résumé (premier semestre)
AtCoderBeginnerContest168 Review & Summary (premier semestre)
AtCoderBeginnerContest178 Review & Summary (premier semestre)
AtCoderBeginnerContest171 Review & Summary (premier semestre)
AtCoderBeginnerContest166 Review & Summary (premier semestre)
AtCoderBeginnerContest161 Review & Summary (premier semestre)
AtCoderBeginnerContest172 Review & Summary (premier semestre)
AtCoderBeginnerContest176 Review & Summary (premier semestre)
AtCoderBeginnerContest180 Examen et résumé
AtCoderBeginnerContest181 Examen et résumé
AtCoderBeginnerContest182 Examen et résumé
AtCoderBeginnerContest183 Review & Résumé
AtCoderBeginnerContest179 Review & Résumé
Résumé du didacticiel Django Girls Première moitié