JOI 2018/2019 春合宿 解説２（Two Antennas, Two Dishes, Two Transportations）
（個人用のメモにつき解読不能です）
＜Two Transportations＞
・小課題１
A = 0
Azer の辺が無い
全ての辺が Baijan にある
→ Baiijan は都市 0 からの距離が分かる
Baijan が距離を求める
距離を Azer に送る
N <= 2000
Dijkstra法 O( (N + B) logB)
N < 2^11，（重み）< 2^9，（距離）< 2^20
→ 頂点番号順に距離を送る 1999 * 20 = 39980 bit
Baijan は InitB 内で SendB を連続で呼び出す
Azer は累計 bit 数を覚えて 20 bit ごとに整数に変換
・小課題２
B <= 1000
Baijan の辺が少ない
→ Baijanの辺の情報を全て送りたい
S_j < 2^11，T_j < 2^11，D_j < 2^9
→ (S_j, T_j, D_j) を送る 1000 * (11 + 11 + 9) = 31000 bit
・小課題３
A + B = N - 1
木である
B <= N - 1 これは多くない
→ Baijanの全ての辺を送れないだろうか
愚直に送ると，1999 * (11 + 11 + 9) = 61900 bit
木の性質を考える
Baijan の持っている辺は森になっている（木の集合体）
「もう少し木の性質を考える」(575)
1 頂点を除いて頂点と辺が対応するようグループ分け
DFS 等で得られる
Baijan の辺を頂点と結びつける
k 回目には頂点 k に対応する辺の情報（反対の頂点，重み）を送る（片方の頂点の情報が省略できる）
1999 * (11 + 9) = 39980 bit
・小課題４，５
N <= 900
特に嬉しい性質無し
「一点から各頂点までの距離を知りたい」
Dijkstra 法を応用できる？
辿る辺の種類で最小値を 2 種類もって遷移する
これを二人で計算する
Azer, Baijan それぞれが持っている辺だけでまず Dijkstra
各頂点との距離を互いに送りあう
そして，それぞれ各頂点との距離を更新（同期）
またそれぞれが計算
また各距離を送りあう
次に近い頂点が分かる
これを繰り返す
各段階で O(N) の通信 → 全体で O(N^2) になってしまう
値が更新されるときだけ送ればいいのでは → 最悪 O(A + B)
ここで，それぞれが送る情報のうち一番小さいものしか必要でない
各段階でそれぞれが持っている最小距離とその頂点番号を送る
各段階で O(1)，全体で O(N)
お互い送ったもの 2 つのうち，距離が小さいものがその頂点で確定
1 頂点あたり送るのは（距離，頂点）* 2 = 62 bit
N <= 58000 / 62 = 935 で解ける
ここで，お互い送る 2 つのうち，大きい方の最小距離と一緒の頂点番号はいらない
改善１：頂点番号は距離が小さいものだけあとからおくる
→（距離）* 2 +（頂点） 20 * 2 + 11 = 51 bit
小課題５まで通る
・満点
Dijkstra 法では距離が小さい順に求まる
ある段階で距離 z が求まる → 次の段階での距離は z 以上
逆に z +（重みの最大）以下
改善２：真の距離の代わりに前段階での距離との差を送る
これは重みの最大 (= 500) 以下なので 9 bit
1 頂点当たり送る情報は 9 * 2 + 11 = 29 bit
N <= 58000 / 29 = 2000
満点が取れた
＜Two Antennas＞
・小課題１
問題文が読めたか
・小課題２
f(l, r) := アンテナペア l, r の通信のしにくさ（or -inf）
dp[l][r] := クエリ (l, r) の答え
dp[l][r] = max(dp[l + 1][r], dp[l][r - 1], f(l, r))
前計算 O(N^2)，クエリ O(1)
・小課題３
abs(h_j - h_i) = max(h_j - h_i, h_i - h_j) (i < j)
abs(h_j - h_i) の max じゃなくて h_j - h_i の max とみていい
こっちのほうが扱いやすい
N がでかいので愚直に全部のアンテナのペアは試せない
r を固定して (1, r), (2, r), … , (r - 1, r) を全部同時に試す→ r を走査
r - b <= l <= r - a ← 区間クエリっぽい
l +a <= r <= l + b ← 走査中にイベントが起こりそう
右端を動かしていく中で，考慮しないアンテナは爆破し，また考慮する必要が生じたら建設する
以下のクエリができればいい：
場所 x にアンテナを構築
場所 x のアンテナを爆破
[l, r] に生えているアンテナのうち，高さの min は？
→ RMQ
O(NlogN) でとけた
・満点
とても難しい，観賞用
基本方針は変わらない，r で走査する
走査中に逐次クエリも答えていく
各 l ごとに i = l + 1, l + 2, … , r についての h_i - h_l の max を d_i とおいて管理する
クエリ (l, r) の答えは max(d_l, d_l + 1, … , d_r)
配列 a_i（最初は inf），d_i（初期値 -inf）にクエリを飛ばす
アンテナ爆破，建設（a_i = inf, a_i = h_i）
区間についてそれぞれ d_i = max(d_i, x - a_i) ← x は今までの max だけ持てばいい
区間の max(d_i) を求める
配列 a_i（最初は inf），c_i（初期値 -inf），d_i（初期値 -inf）にクエリを飛ばす
アンテナ爆破（a_i = inf）
建設（a_i = h_i, c_i = inf）
区間についてそれぞれ c_i = max(c_i, x), d_i = max(d_i, c_i - a_i)
区間の max(d_i) を求める
遅延伝搬セグ木でできる
c_i を伝播する
ノードごとに持たせる情報： c_i = max(c_i, x) を遅延伝搬したもの，a_i の min，d_i の max
O(NlogN + QlogN)で解けた
＜Two Dishes＞
・小課題１
制限時間の制約が全て同じ
取る順序を気にしなくてよくなる．つまり，カレーと丼を制限時間内に取った個数の組から答えが決まる．また，カレーと取った個数から丼を取った個数は一意に定まり，これは二分探索で求められる．O(NlogM)．
・考察
空白の時間はない．丼やカレーの中では手順が決まっているので，ある手順で点数がとれるかはもう一種類の食べ物の手順がどこまで進んでいるかによる．
問題を変換する
N * M のグリッドがあり，マス目の間に左や上から直線が伸びていて，線を通ると点数が得られる．
・小課題２
取り方を全通りためす
・小課題３
取り方を DP で決める
dp[n][m] = max(dp[n - 1][m] + f1(n, m), dp[n][m - 1] + f2(n, m))
f1(n, m) :=上から (n, m) に来た時，線を通るなら P_n，そうでないなら 0
f2(n, m) も同様に定義
・小課題４，５，６
P, Q は正 ← うたがわしい
DP で取り方を定めたいが，無理
テーブルの変化が少ないとうれしい
→ dp[n] に dp[n - 1] のテーブルを使いまわして，更新をさぼれる
テーブルの使い回りをすることにして，元に復元できるように DP をする
dp[n][m] = max(dp[n - 1][m] + f1(n, m), dp[n][m - 1] + f2(n, m))
から，dp[n][m] は max 内の 2 つの式のいずれかと等しく，f1, f2 は n, m それぞれ固定すれば 2 種類しか値を取らないので，差分を取ると変化が少ない気持ちになれる
マスの左に線があれば，dp[n][m] - dp[n][m - 1] = Q[m]
理由：横線はできるだけ左にいたほうが通りやすい（短期的には点がもらえなくなるタイミングまで点を取るのを先送りした方がいい）
dp[n][m] - dp[n][m - 1] - Q[m] も変化が少なそう？→少ない
変化が小さいが，0 以上の性質を保つため，左に線が無いマスには dp[n][m] - dp[n - 1][m] をいれる
横線がないとき，消えた線の右下を (n, m) とすると，dp[n][m] - dp[n][m - 1] >= P[n] のとき，dp[n][m] は変わらないが dp[n][m - 1] は k 増えるので diff[n][m] は減少する
dp[n][m] - dp[n][m-1] < kのとき，dp[n][m] は横から遷移するようになる．さらに，dp[n][m] の値も余って分だけ増えて右に伝播していく
値の加算は縦線の数だけなので O(M) 回
一度の減算で N 回減産すると N - 1 か所消えるので，ならすと値の減少は O(N + M) 回
全体で O( (N + M) log(N + M)) で抑えられる
・満点
P, Q に制約がない場合を考える
上からの遷移は縦の線を通るが，左からの遷移は縦の線を通らないので，縦線が消えたとき，その線の点数 Q[m] が加算される
走査を行で考える
i 行目の P[i] > 0 の横線が消える → 線の右下にあるマスに減算
P[i] < 0 が消える → 線の右下にあるマスに加算
走査を列で考える
i 列目の Q[i] > 0 の縦線が消える → 線の右下にあるマスに減算
Q[i] < 0 が消える → 線の右下にあるマスに加算
→ 行か列かの違いは正か負かの違い
Add(x, v) := diff[x] に v を加算
Decrease(x,v) := diff[x] < v のとき，diff[x] = 0 として y > x かつ diff[y] となる最小の y に対して Decrease(y, v - diff[x]) をする．
そうでないとき，（？？？）
