JOI 2018/2019 春合宿 解説３(Designated Cities, Lamps, Bitaro, who Leaps through Time)
＜Lamps＞
・小課題１
全状態を探索する
0, 1 の状態は 2^N 通り，各状態からの遷移は O(N^2) 通り
BFS で O(2^N * N^2) 時間で分かる
・小課題３
初期状態が全部 0
連続する 1 の区間の個数回の操作でできる（各区間で ON か TOGGLE をする）
それ未満ではできない
01, 10 と並んでいる場所は 1 回の操作で高々 2 か所しか増えない
← 区間の左右の端の部分でしか増えないので
連続する 1 の区間を k 個作るには，10, 01 と並ぶ場所を 2k 箇所作らなきゃいけないので，k回
・小課題２
ON, OFF は先にやっていい
すべての ON, OFF をすべての TOGGLE よりさきにやる最適解がある
直観的な理由：ON, OFF は操作前の列の情報を消す感じ，TOGGLE は保つ感じだから
走査の結果を変えず回数を増やさずに ON, OFF を先に持ってこれることをしめす
TOGGLE と ON がちょっと重なっている場合は TOGGLE の区間が短くなる
ON, OFF に TOGGLE が完全に含まれる場合は TOGGLE の意味がない
方針：
１：OFF, ON が終了した時点で各ランプが，OFF にされた，ON にされた，最初のまま，のいずれかになるか決める
２：初期状態から↑にするための必要な ON, OFF の回数を求める
３：ここから必要な TOGGLE の回数を求める
２：
いじらないところで区切って 0, 1 の連続はまとめて回数を考える
長さ k > 0 の 0101… [1010…] は最小 floor( (k + 1) / 2) 回
→ 0101… なら全体を OFF にしてから ON を floor(k / 2) 回すればいい
３：
1001010110 -> 010010111 は 000000000 からそれぞれを XOR した値にするのと一緒
１：
DPをする
状態：今何文字目までみたか，直前は 0, 1, ? のどれか，今作っている 0101… [1010…] の部分の長さ
遷移：次を 0, 1, ? のどれにするか
回数計算：0101… を閉じるときに ON, OFF の回数を足す，目標との XOR が 0 から 1 になるときに足す
O(N^2) 時間，O(N^2) メモリ
・満点
効率のいい回数計算
長さの偶奇が繰り替わった時に回数は 1 増える
なので，今作っているのは 0101… か 1010… かどっちかを持っておけばいい
5N 状態ぐらいで，O(N) 時間，O(N) メモリ
実は，ON, OFF をする区間は重ならなくていい，隣接しなくていい
重なっているのは無駄（それはそう），隣接しているのは OFF と TOGGLE の組み合わせで十分
0, 1, ? の列としては 0 と 1 が隣接しないものだけを考えればいい
DP の状態を 3N くらいにできる
＜Designated Cities＞
・小課題１
N <= 16
2^N 通り選ぶ頂点を全探索して DFS する
O(N^2 * 2^N)
・小課題２
Q = 1，選ぶ頂点は１個
木 DP する
O(N)
・小課題３
Q = 1，選ぶ頂点は２個
木 DP する
O(N)
コストを 0 にした辺の最大かする
選んだ２つの頂点を結ぶパスは双方向タダになっている
各辺について，双方向のコストを足したものをもっておくと嬉しい
各頂点についている部分木の中でパスのコストの総和が大きいもの２つを採用するなど
・小課題４
N <= 2000
選ぶ頂点が１個の場合は小課題２でできるのでそれ以外の場合を考える
木の葉の個数以上選べるときは，葉を全部選べばコスト０
木の葉の個数未満しか選べないときは，選ぶ頂点は全部葉（葉でないものを選んだ場合は適当な葉に向けて鵜がした方が得になる）
選ぶ葉を固定する（O(N) 通り）
選んだ頂点を根にして考える
根に向かう頂点のコストは全部０になっている
辺のコストは葉に向かうものだけ考えればいい
葉を１つ指定すると根からその辺へ向かうパスのコストが０になる
葉をいくつか選んで葉ー葉のパスのコストを最大化することになる
実は，選ぶ葉は貪欲に選んでいい（次に選ぶと増えるコストが最大のものを選ぶ）
最初に選ぶ葉ー葉のパスがあってればあとは再帰的に求められる
葉ー葉のパスを１つの頂点にして，その頂点から他の葉へ辺を張る形に変形できる
SegTree で頑張る
めんどくさい
priority_queue で頑張る
まず，queue に最大コストのパスを push する
以下を繰り返す：
・queue から最大コストのパスを取り出して使う．パスを使うことによって，気がいくつかの部分木に分かれる
・分かれる各部分木の最大パスを queue に push する
こっちのほうが簡単 O(NlogN)
決めうつ葉を O(N) 通り試すので，合計 O(N^2 logN)
・小課題５
これいるか？面倒な割に満点解法につながらない
先の解法で queue に push されるコストの集合を考えて，根として選ぶ頂点を（葉に限定しないで）一つ隣の頂点に移動した場合の変化を見る
変化の回数は一回の移動当たり定数解なので解ける
・満点
葉を全部試すのは大変
実は，２個選ぶときの解で選ぶ頂点のうち一つを適当にとってくる（R とする）と，２個以上選ぶときの解であって R を含むものが必ず存在
証明：
K 個選ぶ解であって，R を含むものが存在すると仮定
K = 2 は自明
K + 1 個選ぶ解を任意にとる
ある解に対して，選んだ２頂点間のパス上に存在する点を内点と呼ぶ
K 個選ぶ解と K + 1 個選ぶ解で，内点が共有されている場合，そこを起点にさっきの貪欲をすれば同じ解が得られるはず
内点が共有されてない場合，K + 1 個の解で選んだ頂点のうち適切なものを取ると，それを K 個の解に付け足すと K + 1 個の解と比べて損しない解が得られる
根として固定する葉は１つでいいので，O(NlogN)
＜Bitaro, who Leaps through Time＞
・小課題１
移動クエリごとにシミュレーション
タイムリープ数が同じなた，同じ年につく複数の行動のうち，到着時間が一番早いものが嬉しい
目的地とは反対の都市へ移動する必要はない
都市 A から B (A < B) に移動するときは，都市 A, A + 1, … , B の出発・到着時刻だけ考えればいい
各都市での待機・タイムリープは必要最小限でいい
各都市の出発・到着時刻も整数値のみ考えればいい
O(NQ)
・小課題２
変更クエリが無い
都市 A から B (A < B) への移動のみ考える
A > B のときは都市の順番をひっくり返せば OK，A = B のときは自明
都市の移動に一秒かかる → 斜め移動はめんどい
時間軸をゆがめて，都市iの時刻がiだけ進んでることにする
移動コストは０，移動クエリ (B - A, D - C)，道路 (L - i, R - (i + 1))
これで真横に進む感じで考えられる
↓
長方形のクエリが並んでいる
以下のクエリを処理する：
・ブロックの位置を変更する
・指定された始点から終点まで計算するときの下方向移動コストの最小回数を計算する
あるブロックにぶつかるような経路は，その後は同じような経路をたどる
最初にぶつかるブロックとは？
ある頂点から右に移動したとき，最初にぶつかるブロックは O(N) で計算できる
deque を使って左側からスキャンするなどすると，頂点 K 個に対して O(N + K) で計算できる
→ x = 1 から x = N までスキャンしていく
→ x = k でぶつかる頂点をキューから除き，x = k な頂点をキューに追加
各移動クエリの始点＋ブロックの角に関してそこから右側に進んだとき最初にぶつかるブロックを求める
すると，各視点から右側に進んだとき 2^k 回目にぶつかるブロックが求められる → ダブリング
ブロックを回避するためのコストも同時に求められる
ダブリングで 2^k 回目にぶつかるブロックとそこまでのコストを求めておく → O( (N + Q) log(N + Q) )
各移動クエリに対して終点にたどり着く前に最後にぶつかるブロックとそこまでのコストを計算する → O(logN)
変更クエリがないので，全体で O( (N + Q) log(N + Q) )
・満点
変更クエリあり
２つの連続する長方形の隙間は，２つの隙間に共通する空間をつくる１つのブロックと同じとみなせる
また，通過後の座標と下への移動回数が一致する
→セグ木？
共通する隙間の無いものに対しても，座標後の座標が一致するものはある
また，通過後のコストがおおよそ一致するものもある（定数だけずれる）
座標とコストを同時に一致させるようなものは存在しないことがあるのでうまくマージできない
各区間は以下の２つ：
・タイプ１：通過後の座標・コストが１つのブロック対と通過した時と一致する
・タイプ２：通過後の座標は一意に定まり，コストはある上ブロックを通過した時と定数を除いて一致する
キーポイント：これらの区間を合成しても，ふたたび２パターンのどちらかの種類の区間になる
座標をどうマージするか
空いてる場所について共通部分があるなら，合成結果は共通部分だけ空いてるブロック対になる
共通部分がないなら，通過後の座標は右のブロック対の端点のどちらか
コストをどうマージするか
左がタイプ１のとき，右の区間のコスト担当の上ブロックについて，
・左側の上ブロックより小さいとき，合成語は左の上ブロックとと一致
・そうでないとき，合成語はとある上ブロック＋定数と一致
左がタイプ２のとき，
・左の区間を通ると座標は一意に決まる
・右の区間を通るコストも一意に決まる
もちろん，各区間で足される定数コストも足す
座標が１つのブロックを通過した時と一致するとき，コストのブロック対は座標のブロック対と一致するのか？
タイプ１を２つ足したときだけ一致する
タイプ１を２つ足すとタイプ１，２のどっちかにしかならない
・満点
それぞれのブロック対を葉ノードとするセグ木を構築する
変更クエリについて，セグ木を更新 O(logN)
移動クエリ (x1, y1) -> (x2, y2) について，x = x1 から x = x2 の間にあるブロック対をすべてマージし，コストと座標を計算 O(logN)
全体で O(QlogN)
