ARC 073 E - Ball Coloring

• 問題

問題概要

N組の計2N個の整数x_i,y_iを赤/青に分けていく.
(Rmax - Rmin) * (Bmax - Bmin) を求めよ.
1 <= N <= 2*10⁵, 1 <= x_i,y_i <= 10⁹

解法

全体のmax,minであるma = max_i(max(x_i,y_i)), mi = min_i(min(x_i,y_i) は必ずR/Bに塗られているため,
Rmax = ma or Bmax = ma と, Rmin = mi or Bmin = mi が成り立つ.
よって以下の2通りに場合分けして良い.
1. Rmax = ma , Rmin = mi 2. Rmax = ma , Bmin = mi これは貪欲とかで解ける.
簡単のために x[i] < y[i] として, xの昇順に並べておく.
1.は minimize( Bmax - Bmin) であり, 最初xを全てBにし, 小さい方からRに塗ってその分のyをBに加えていけば良い.
公式解説とかこことかが詳しい.
2.はminimize(ma - Rmin) * (Bmax - mi) であり,
これはma >= Rmin と Bmax >= mi から maximize(Rmin) & minimize(Bmax) すれば良いので,
大きい方をRに, 小さい方をBに加えていけば良い.

自分が少しハマったのは以下.
- ma,miのペア ma = x[argma] である場合の y[argma] とかの処理がめんどくさい
- maが複数ある場合どれを取れば良いのか
でもこんなものは無視していいと相場が決まっている(ほんとか？)

まず2.について,大きい方をRに,小さい方をBにしていくと自明にmaはRに,miはBになる
x[i] = y[i] = ma みたいな場合も確実にどちらにもmaが含まれるので考えなくて良い.
よって2.はどれがma,miであるかを考えずに処理していっても大丈夫

次に1.について,正直に処理するならmi=x[0]を除くxを全てBに加え, y[0]だけをBに加える必要がある.
しかしこれは, 最初にxを全てBに加え,小さいものを一つずつ交換していく手順で解けば1回目の操作でmi=x[0]はRに加えられるので問題ない.
また,途中で ma = y[argma] を x[argma]と交換してしまい, Rmax = ma でなくなることもあるが, これも無視して Rmax = ma で計算して問題ない.
なぜならこれ以降ではRmin = mi, Bmax = ma であり,2.の場合で計算していることになるから.
これ以降の計算では最適解よりも大きい値が得られ,minを考える上で影響がない.

よってma,miのペアを無視して計算していいことがわかった. するとどのma,miを取れば良いかという問題もなくなり2個目の問題も解決した.

メモ

難しかった. 数列の操作で最適化する問題なかなか慣れない.

コード