NOMURA プログラミングコンテスト 2021 (AtCoder Regular Contest 121)

#総合結果
* [Score] 900 pts
* [Time] 48:50 + <font color="red"> 05:00 $\times$ 1 </font> = 53:50
* [Ranking] 607 th [Rated内: 576 th]
* [Performance] <font color=#0000FF> 1717　</font>
* [Rating] <font color=#0000FF> 1988 </font> → <font color=#0000FF> 1963 </font> (-25)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#804000> A問題 </font>|400 pts|14:05|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/arc121/submissions/22990737)|[■](https://atcoder.jp/contests/arc121/submissions/23014820)|
|<font color=#008000> B問題 </font>|500 pts|48:50|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc121/submissions/22997232)||
|<font color=#0000FF> C問題 </font>|0 pts|--:--|<font color="red"> (1 Penalty) </font>|||
|<font color=#FF8000> D問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF8000> E問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF0000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>900 pts</b>|<b>48:50</b>|<b><font color="red"> 1 Penalty </font></b>|||

#問題ごとの略解
##<font color=#804000> A問題 (400pts, diff: 459) </font> [2nd Greatest Distance](https://atcoder.jp/contests/arc121/tasks/arc121_a)

以下の事実を用いる. ただし, $p_i=(x_i, y_i), \operatorname{dist}((x,y),(x',y'))=\max (|x-x'|, |y-y'|)$ とする.

> $\operatorname{dist}(p_i, p_j)$ が全ての点対において2番目に大きいならば, $x_i, x_j$ はそれぞれ昇順または降順1番か2番である. $y_i, y_j$ についても同様である.

この事実をもとに, $x_i, y_i$ のうち, 少なくとも一方が昇順または降順1番 or 2番であるような添字をすべて列挙し, この添字に制限すれば, このような添字は高々16個なので, これらは全探索しても十分高速である.

##<font color=#008000> B問題 (200pts, diff: 1159) </font> [RGB Matching](https://atcoder.jp/contests/arc121/tasks/arc121_b)
まず, 赤, 緑, 青の犬が偶数匹であるならば, 同色の犬をペアにすることによって, 不満度の総和を $0$ にすることが可能である. よって, 以下ではそうでないと仮定する.

ここで, 今, 犬は合計偶数匹ということから, 赤, 緑, 青の犬の数のうち, ちょうど2つが奇数である. 以下, 赤, 緑の犬が奇数匹, 青の犬が偶数匹であるとする. このとき, 以下の事実が成り立つ.

> 不満度の総和を最小にする犬の分け方において, (赤, 緑), (緑, 青), (青, 赤) の犬のペアはそれぞれ高々1つずつである.
> (証明): (赤, 緑) の犬のペアが2つあったとし, そのペアが $[r_1, g_1], [r_2, g_2]$ であったとする. このとき, この2つのペアを $[r_1, r_2], [g_1, g_2]$ に変更すると, 変更後の $[r_1, r_2], [g_1, g_2]$ における不満度が $0$ になり, この変更によって, 不満度の総和が増えることはない.

また, 赤, 緑の犬が奇数匹, 青の犬が偶数匹 という仮定と合わせて, 不満度の総和を最小にする犬の分け方において, 色の異なる犬のペアとしてありうるのは,

* (赤, 緑) が1組
* (赤, 青), (緑, 青) が1組ずつ

に限られる. 以下, $R,G,B$ でそれぞれ赤, 緑, 青の犬のリストとする.

* (赤, 緑) が1組について
この分け方における不満度の総和の最小値は
$$\min_{\substack{i \in R \\\\ j \in G}} |a_i-a_j|$$
である. これは各 $i$ を固定したとき, $a_{j_{i,1}} \leq a_i \leq a_{j_{i,2}}$ なる $j_1, j_2$ が存在するとき $\min (|a_i-a_{j_{i,1}}|,|a_i-a_{j_{i,2}}|)$ となることから,
$$\min_{\substack{i \in R \\\\ j \in G}} |a_i-a_j|=\min_{i \in R} \min (|a_i-a_{j_{i,1}}|,|a_i-a_{j_{i,2}}|)$$
である. なお, $j_{i,1}, j_{i,2}$ が存在しない場合は形式的に $a_{j_{i,1}}=-\infty, a_{j_{i,2}}=\infty$ とする.

* (赤, 青), (緑, 青) が1組ずつについて
上の場合ど同様にしてそれぞれ (赤, 青) における不満度の最小値と (緑, 青) における不満度の最小値を求めることができる.

ここで, 2つの不満度の最小値をとる青犬がかぶってしまう可能性がある. ここで, この状況における 赤, 緑, 青色の犬の可愛さを $r,g,b$ とする.

* $r,g  \leq b$ または $b \leq r,g$ のとき, この赤と緑の犬同士でペアを組むと $|r-b|+|g-b| \leq |r-g|$ になる.
* $r \leq b \leq g$ または $g \leq b \leq r$ のとき, この赤と緑の犬同士でペアを組むと, $|r-b|+|g-b|=|r-g|$ になる.

よって, このことから, もし希望する青色の犬がかぶってしまった場合, 不満度の総和は(赤, 緑) が1組についての結果以下になることは無いので, 考慮しなくても良いことがわかり, 上で述べた2つの結果の和を採用しても問題ないことがわかる.

以上の2パターンそれぞれにおける結果のうち, 小さい方が答えである. 計算量は二分探索とそのためのソートがボトルネックになり, $O(N \log N)$ である.


##<font color=#0000FF> C問題 (300pts, diff: 1856) </font> [Odd Even Sort](https://atcoder.jp/contests/arc121/tasks/arc121_c)
(正解でき次第更新予定)

##<font color=#FF8000> D問題 (400pts, diff: 2748) </font> [1 or 2](https://atcoder.jp/contests/arc121/tasks/arc121_d)
(正解でき次第更新予定)

##<font color=#FF8000> E問題 (500pts, diff: 2645) </font> [Directed Tree](https://atcoder.jp/contests/arc121/tasks/arc121_e)
(正解でき次第更新予定)

##<font color=#FF0000> F問題 (600pts, diff: 2940) </font> [Logical Operations on Tree](https://atcoder.jp/contests/arc121/tasks/arc121_f)
(正解でき次第更新予定)