ABC127 DEF メモ - tinumu's reminder

not-522.appspot.com
tinumukiti631.hatenablog.com
これの続きね

D - Integer Cards

同じ場所を $2$ 回書き換えるのは明らかに無駄
つまり $N$ 回書き換えるのを最大化すればいい
これは、元のカードを小さい順に並べ替えて、追加するカードを大きい順に入れていけば、最適
まあそうだね

E - Cell Distance

これ難しいね

答えは、 $\sum\sum\limits_{i}\sum\limits_{j} (|X_i - X_j| + |Y_i - Y_j|)$ となる。
(左の $\sum$ は $K$ 個の点を選んだ時の組み合わせの集合すべての和の意味として使ってます)
ところで、点 $i$ と点 $j$ については考えているけど、他の点は遊んでいる。
そのため、 $2$ 点だけ先に決めて、後で $K-2$ 点を決めることが出来る。
ここで式は $\sum\limits_{i}\sum\limits_{j}\sum (|X_i - X_j| + |Y_i - Y_j|)$ となる。
$K-2$ 点を決めても答えは変化しないので、 $|X_i - X_j| + |Y_i - Y_j|$ の答えが $_{NM-2}\mathrm{C}_{K-2}$ 個だけあることになるので、更に式変形でき、
$\sum\limits_{i}\sum\limits_{j} (|X_i - X_j| + |Y_i - Y_j|) \times _{NM-2}\mathrm{C}_{K-2}$ となる。

ここまで来ると、計算量が $\mathrm{O}(N^2M^2)$ くらいに落ちている。
あとは $\sum\limits_{i}\sum\limits_{j} (|X_i - X_j| + |Y_i - Y_j|)$ を高速化できればいい。

まず、 X 座標と Y 座標を分解して考えられるので、
$\sum\limits_{i}\sum\limits_{j} (|X_i - X_j| + |Y_i - Y_j|) = \sum\limits_{i}\sum\limits_{j} |X_i - X_j| + \sum\limits_{i}\sum\limits_{j} |Y_i - Y_j|$ となる。

X座標について考えてみる。
$2$ 点の距離が $i$ である時、縦に決められる座標の場合の数が $N^2$ 通り、横に決められる座標の場合の数が $M-i$ 通りあることから、
総距離は、 $N^2(M-i)i$ だけある。 $i$ は $0$ から $M-1$ までありえるので、全て足して、
$\sum\limits_{i=0}^{M-1} N^2(M-i)i$ が得られる。
Y座標についても同じように求めると、
$\sum\limits_{i}\sum\limits_{j} |X_i - X_j| + \sum\limits_{i}\sum\limits_{j} |Y_i - Y_j| = \sum\limits_{i=0}^{M-1} N^2(M-i)i + \sum\limits_{i=0}^{N-1} M^2(N-i)i$ となり、 $\mathrm{O}(N+M)$ で求められる形になる。

$_{NM-2}\mathrm{C}_{K-2}$ の計算が一番かかり、
$\mathrm{O}(NM)$ で答えを求めることが出来る。

うわ　何だこの解説　解説にもなってねえ

F - Absolute Minima

$b$ は定数なので、無視！(素振り)
傾きが $0$ になっているところをずっと持っておけばいい。
なぜなら、新たなクエリを追加しても、傾きが $0$ になっている部分から関数の下限が求まるからである。
他の部分の傾きの絶対値は $1$ 以上となっており、そのような点は傾きが $0$ になっている点よりも関数の値が下回ることはない。

では、どうやってそのような位置を求めれば良いのか。

ここで multiset を 2 つ用い(ls, rs としておく) $-1$ の傾きと $1$ の傾きを表現する。　この時、 $-1$ の傾きが始まる座標が $1$ の傾きが始まる座標よりも必ず左にあるようにすると、 *ls.rbegin() から、*rs.begin() までが、傾き0の座標ということになる。
f:id:tinumukiti631:20200309171927p:plain
こんな感じで
*ls.rbegin() より左に $a$ があるようなクエリや、 *rs.begin() より右に $a$ があるようなクエリが来た場合、ls, rs の順序が崩れるので、　傾きが交差するところを適切に張り替えると順序を保つことが出来る。またそのようなときは、下限が上がるので、計算を忘れないようにしたい