JOI 2018/2019 春合宿 解説１(Examination, Naan, Meetings）
（個人用のメモです，間違いがある可能性があります）
Examination
小課題１
N, Q が小さい
愚直に合否判定をして間に合う
O(NQ)
小課題２
Z_j = 0 より合計点は合否に影響しない（無視できる）
数学が X_j，情報が Y_j 以上の人数を数えたい
二次元平面上にプロットすると，ある右上の領域
クエリを X_j の大きい順にソートして，数学の合格基準と下げていくことを考える
新たに数学で基準に満たした生徒について，T_i の値を記録する
→ 数列 B_1, b_2, … （初期はすべて 0）について b_(T_i) に 1 をたす
Y_j 以上の値がいくつあるかを求める
→ b_Y_j, … の和を求める
これは BIT で求められる
O((N + Q)(logN + log(max(得点))))
小課題３
合計点も合否に影響してくる
X_j + Y_j >= Z_j のときは合計点の制約を無視できる
→ このようなクエリは小課題２の解法を流用する
問題は X_j + Y_j < Z_j のとき
合計点が Z_j 点以上の生徒のうち，数学と情報も合格基準を満たしている人数の数え方を考える
合計点の合格基準を満たしている生徒のうち，数学・情報が満たしている人数は小課題２の方法で知れそう
Z_j の大きい順にソートする
２つの BIT を用意：数学の得点用，情報の得点用
合計が Z_j 以上の生徒について，２つの BIT を用いる
クエリでは (数学合格) + (情報合格) - (それまでに追加した生徒数)
計算量は小課題２と同じ
小課題４
点数の値が大きい
点数について座圧をすれば実質小課題３と同じ
O((N+Q)logN)
別解１：二次元セグ木
座標平面に点を追加，矩形範囲の点の個数を求める
セグ木のそれぞれのノードにセグ木を載せる
全体のセグ木上で横の範囲のノードまで移動，ノード内のセグ木で縦の範囲のノードまで移動，あとは両方とも親へ伝播する．求めるのも同じ．
空間計算量が O(N^2) となり MLE になってしまう
クエリを先読みして，使われる値だけに座標圧縮して減らす
別解２：定数倍高速化
O(NQ) を定数倍高速化することで AC できる
#pragma GCC target("avx2") // CPU 処理並列化
#pragma GCC optimize("O3") // CPU 処理並列化
#pragma GCC optimize("unroll-loops") // 条件処理の呼び出しを減らす
！GCC のバグがあるかもしれない（WAになるかも）
！コンテスト，サイトによっては使えないかも
得点分布
(点数, 人数) = (2, 3), (22, 5), (100, 13)
Naan
本当に Impossible か？
少なくともサンプルになかったら怪しい… 今回は常に可能
小課題１
嬉しい，点数が増える，より高い点数の解法のヒントになる
だいたい「真ん中」で切って分けたい → 真ん中ってどこ？
本当に半分に切るのは全然だめ
２人の重みの総和が半分になるところで切る
どっちもどちらかの人が大きくなることはあり得ないので
でも，いっぱんの N には拡張できない
人１の重みが半分になるところで切る，これでも OK
人１にはどっちを渡してもいいので，人２により嬉しい方をあげる
小課題２
いっぱんの N にするとどうなる？
前と同じようにできるか？→ だめ
左端をめちゃくちゃ食べたがっている人に左端をあげるとよさそう
左端から各人が食べたい位置を計算し，その中で一番左になる人を選んでそこで切って，そのピースをその人に上げる
そうすると，各のこった人について，残った何のの重みの割合は (N - 1) / N 以上になる
残ったナンを使って残った N - 1 人で分ける（再帰的に）
これでもまだ満点ではなく，B_i <= 10^9 という制約がある
初めに切るところは (整数) / N の重みをもつので，左端からの距離は (整数) / (N + V_ij) みたいになる
その後再帰すると，全体の重みの和が整数ではなくなり，切る場所の分母が大きくなってしまう（N * V * (N - 1) * V）
ここではセーフ
満点
はじめの一人については一緒
次は，ナンを切らなかったとして 2 / N で同様のことをする
→ 各人について2 / Nになるところを求めて，一番左になるもの
これを進めていく（3 / N, 4 / N, … と求めて，まだナンをもらってない人の中で一番左になるものを採用）
変に切ったりしていないので分数もめちゃくちゃにならない
O(NL)
得点分布
(点数, 人数) = (0, 4), (5, 4), (24, 2), (29, 11)
Meetings
小課題１
全ての木を全探索する（苦行）
小課題２
ありうるクエリは 19600 通りしかない
クエリをメモ化すれば TLE しない限りとける
頂点 u, v が直接つながれているかどうかを求めたい
小課題３
頂点 u についてつながってる変全てを求める
頂点 1 について 2~N とのクエリを実行（？）
解けていない (最悪 2 * n ^ 2 回のクエリ)
枝狩りをする
ある頂点 u について調べるとき，for(i) の部分は u < i のものだけ調べればよい
想定解は違う
クエリごとにすでに気が存在したときにそれに対して新たな頂点がどのようなつながり方（間に入るとか）をするかを考える
重心分解をして，つながり方の頂点をうまく聞くと解ける
別解
適当な木がある
適当に２頂点を選ぶ（p1, p2とおく）
query(p1, p2, i) (i は全ての頂点) を投げる
p1 - p2 のパス上にある部分木を得る
部分木ごとにクエリで得られる数が違う（種類が分かれる）
（ここから先が分からなかった）
得点分布
(点数, 人数) = (100, 3), (78, 1), (29, 10), (17, 6)
