AtCoderBeginnerContest178復習＆まとめ（後半）

AtCoder ABC178

2020-09-13(日)に行われたAtCoderBeginnerContest178の問題をA問題から順に考察も踏まえてまとめたものとなります．
後半ではDEの問題を扱います．前半はこちら
問題は引用して記載していますが，詳しくはコンテストページの方で確認してください．
コンテストページはこちら
公式解説PDF

D問題　Redistribution

問題文
整数$S$が与えられます。 すべての項が$3$以上の整数で、その総和が$S$であるような数列がいくつあるか求めてください。ただし、答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを出力してください。

かなり苦戦しました．
$a_n$を$S=n$のときの答えとすると以下の漸化式が成り立つので，漸化式を順に計算していくことで答えを求めることができます．
$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問題　Dist Max

問題文
二次元平面上に$N$個の点があり、$i$番目の点の座標は$(x_i,y_i)$です。 同じ座標に複数の点があることもあります。 異なる二点間のマンハッタン距離として考えられる最大の値はいくつでしょうか。
ただし、二点$(x_i,y_i)$と$(x_j,y_j)$のマンハッタン距離は$|x_i−x_j|+|y_i−y_j|$のことをいいます。

問題見た当初は，点をいくつか結んで，その内側の点は考えなくて済むなーとか思いつつ，最初に選ぶ点をなるべくはじのものにしたいなと思っていたら，解き方に気づきました．やっぱり図を書くって大事ですね．

$x_i+y_i=k_i$から，$(1,1)$に一番近い点($k_i$が最小となる点)と$(10^9,10^9)$に一番近い点($k_i$が最大となる点)を求める．
$-x_i+y_i=n_i$から，$(10^9,1)$に一番近い点($n_i$が最小となる点)と$(1,10^9)$に一番近い点($n_i$が最大となる点)を求める．

$k_{max}$と$k_{min}$のマンハッタン距離か$n_{max}$と$n_{min}$のマンハッタン距離が，考えられるマンハッタン距離の最大となる．

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

個人的には普段の問題セットと比べ，E問題までソースコード自体はシンプルで，数学？を使う問題が多かったので，好きな問題セットでした．

後半も最後まで読んでいただきありがとうございました．