AtCoder Regular Contest 100

AtCoder Regular Contest 100に参加しました！
ABC102 beta:
https://beta.atcoder.jp/contests/abc102/beta.atcoder.jp
ARC100 旧版:
arc100.contest.atcoder.jp
ARC100 beta:
https://beta.atcoder.jp/contests/arc100/beta.atcoder.jp

解けた問題だけ解説をしていきますー

要項

AtCoder Beginner Contest 102 / Regular Contest 100
rated 1200 / 2800
7/1(日) 20:30 ～ 22:10 (100分)
100-200-300-600-700-1100 (6問)
ペナルティ: 5分

方針

前回の失敗分のレートを取り返すことを考えると3完しかないけど、時間が足りないかも
とりあえず2完をして、最低限は維持したい

A - Multiple of 2 and N

$N$ が2の倍数ならば、明らかに答えは $N$ です。
そうでないなら $2N$ が答えになります。

まず、 $A_i > A_j$ であるとします。この時絶対値記号は外せますね。
$A_i - A_j$ について、ある $k$ が存在して $A_k > A_i$ だったとします。
この時、明らかに $A_k - A_j$ の方が差が大きくなるので、まず $A_i$ は $A$ の最大値であることが分かります。
逆に $A_j$ についてある $k$ が存在して $A_j > A_k$ ならば $A_i - A_k$ の方が差が大きくなるので、 $A_j$ は $A$ の最小値であることが分かります。
よって最大値の要素から最小値の要素を引いた値が答えになります。

C - Linear Approximation

まず、 $B_i=A_i - i$ を定義すると、この問題は $\sum_{i=1}^N |B_i - b|$ を最小化する問題になります。
ここで、ある $b$ について $b$ より小さい $B_i$ の個数を $x$ 個とします。
この時、 $b$ を1増やすと $x$ 個は距離が1離れ、 $N-x$ 個は距離が1近づくので結果的に悲しみは $N-2x$ だけ減ります。
ということは、 $x=N/2$ の時、つまり $b$ が $B_i$ の中央値の時に答えは最適になります。