JOI 2018/2019 春合宿解説４(Cakes 3, Mergers, Minerals)

（個人用のメモにつき解読不能です）

<Minerals>
・小課題１
C(2N, 2) 個のペアについて全部試す
O(N^2) 回装置を使う

・小課題２
O(NlogN)ぐらいなら通るか
分割統治で再帰てきに解く
半分に分けたものを全て機械に入れる
もう片方から１つ持ってきて種類数が増えるか増えないか
集合サイズが１になるまで log N ステップかかる
それぞれに対し，
・左の半分を装置に入れる
・右のそれぞれを入れて，取り出す
・左の入れたものを出す
O(NlogN)

・小課題３
グループ分けがない
２つの {1, …, N} グループに分類
4N 回あれば２つに分けられる
切片１から順に追加
非登場・登場ずみでグループがつくれる
一つ一つ順に追加するので 2N 回
きれいにするので 2N 回
合計 4N + 3NlogN < 70 万

・満点
着眼点１：いちいちキレイにする必要はあるか？
分けたい２つの分類の外は放置していいし，分けたいところも in / out を変えるべきものだけかえればいい
→終わった後きれいにする必要はない
最初は 2N 回
分割統治 logN ステップ
それぞれ 1 ~ N : N / 2 回
N + 1 ~ 2N : N 回
あわせて 2N + 1.5N logN 回
ちょっと節約できた

着眼点２：本当に N + 1 ~ 2N 全部出し入れする必要あるか？
→ ない
各再帰ステップの中で，最後の１個（２個）は追加する必要がない
再帰の呼ばれる回数は 2N 回くらい
これで最低 2N 回減った

そもそもクエリの答えの増加・減少に意味はあるのか？
増加・減少ではなく，増減に意味がある
１個余ったものもそのまま放置していい

Random Shuffle
・Random_shuffle(a, a + N)をする
・for (int i = 0; i < N; ++i) swap(I, rand() % (i + 1));
O(N) でランダムな順列の一つを等確率で作れていい

着眼点３：本当に二等分がいいのか？
p = 0.38ぐらい
DPで最小回数を達成するための分割方法を求めることができる

１：一回一回きれいにしなくていい
２：最後の一個はみなくていい
３：半分でなく分ける

<Cake 3>
M 個のケーキを選んだ後に，隣り合う C の差の絶対値の総和を最小にする並び替えを考える
C が小さい順に並べるのが最適
（選んだ V の総和）ー（選んだ C の最大値 - 最小値）* 2

・小課題１
C の最小値・最大値を決めて，その間のケーキのうち V の大きい方から M 個とる

・小課題２
ケーキを (Ci, Vi) の順にソートする
区間の左端を固定し，右端を右方向に動かす
priority_queue等を使って O(N^2 logN)

・満点
O(N) ぐらいに減らしたい
各左端に対して，最適値を取る右端のみを調べられるとうれしい
分割統治を用いる
探索区間の面積は毎回 1 / 2 ずつ減っていくので，O(N logN)
Monotone minima というらしい
IOI 2014 Holiday

[l, r] 内の値の大きい方からM個の総和とは？
分割統治で必要になる値の [l, r] の順序をうまいこと利用したい
区間 [I, i] からスタートして右端を伸ばすことなら O(logN) でできる
左端を縮めることもできるのでは？ → できる
右端を伸ばす・左端を縮めることを区間ごとに繰り返す
毎回見なきゃいけない区間が左端・右端とも単調増加になっているので嬉しい

・値を集合に加える
・値を集合から削除する
・追加されて残っている値のうち最大 M 個の総和を求める
のクエリを処理できるデータ構造がほしい

平衡二分木解
std::set では k 番目の値を求める操作がサポートされていないので，g++ 拡張の tree を使う
定数倍が怪しい

セグ木解
一点更新・区間和のセグ木を２本用意
Vi の順に並べたながさ N の数列を考えて各節には区間内の生きている個数と V の総和を持つ
あとは，セグ木上で二分探索で右からの個数の和が M になる位置を求め，そこから末尾までの V の総和を普通にとればいい
各クエリ O(logN)

<Mergers>
同じ週に属する頂点が同じ集合に属するように気を二つの連続部分木にわけることができるか

・小課題１
州のマージの仕方を全列挙
K! を超えないことがわかる
O(K! 2^K N)

木を二つの連結部分木に分ける → 一つの辺できる

・考察
二つの頂点を選んで，それらの間にある辺を全て集約することを繰り返して，一点に潰す
これを何回行えばいいか？
（葉の数＋１）/2
葉の数が３つでなければ，一回の操作で２つ潰せる
集約した木の葉を数えればいい

・小課題３
Kが小さい
各州について，それによって集約される辺の集合はその週に属する２頂点を結ぶパスすべての集合
頂点も同様

・小課題４
熱危機にして考えて，２頂点の間のパスを求めるには，LCA まで気を上に登ればいい

・満点
パスの長さが長いかもしれない→パスに含まれる辺を列挙できない
LCA は O(logN) で求められる
累積和を使う
選んだ２頂点に +1，LCA の頂点に -2 を加算する（すべてのペアについて），下から累積和を取る