刑務所(Jail)解説 nxteru (戸高空)問題概要

 𝑁頂点の木に𝑀人の人がいる 人𝑗は最初頂点𝑆𝑗 におり頂点𝑇𝑗 に移動させたい ある人を他の人がいない隣接した頂点に移動させるという操作を好きなだけできる（同時に2人以上が同じ頂点にいてはならない）
 全員が最短経路で遠回りをせずに移動をすることはできるか 𝑁, 𝑀 ≤ 120 000

小課題１

 𝐴𝑖 = 𝑖，𝐵𝑖 = 𝑖 + 1
 木はパスグラフである

小課題１
 直線上を人が左右に移動するとみなせる
 移動前と移動後で人の並びの順番が一致している⇔Yes なぜか？
 一致していない⇒どこかで人のswapが必要なのでNo 一致している⇒誰かを隣り合う頂点に移動させることで終わりの状態に近づくような移動が常に存在する

小課題２

 𝑄 ≤ 20，𝑁 ≤ 250，𝑀 = 2
 Noになるような位置関係で適当な場合分けをすればよい 2人のいる場所の状態は𝑁 2 通りしかないのでDPでも解けるここで大胆予想

ここで大胆予想 ある人の移動を複数回に分けて行う必要って本当にあるの？

ここで大胆予想 ある人の移動を複数回に分けて行う必要って本当にあるの？

 実は「Yes⇒同じ人の移動はすべて連続して行うような移動のさせ方が存在する」ことが証明できる

証明・・・ １２２３２３４１ ・・・

 Yesである仮定したときそれを達成するような移動のさせ方で、操作で指定する人を順番に並べた列を考える

証明
X・・・ １２２３２３４

Y

１ ・・・

 ある人にとって連続するが操作の列では離れている2つの操作に注目（𝑋, 𝑌とする）

 ここで𝑋の前に操作の列で連続している同じ人の移動、𝑌の後に連続している同じ人の移動もひとかたまりとして扱う

証明
X・・・ １２２３２３Y４１ ・・・YX

 その2つが右図の移動

A

B

C

証明
X

・・・ １２２３２３

 その間人1は頂点𝐵にいるので緑の区間の移動は𝐵を通らないY

４１ ・・・

YX
A

BC

証明
X

Y・・・ １

１ ・・・

 𝐵で分けたときの部分木ごとに間の操作を分類する

AB

C

証明
X

Y・・・ １

１ ・・・

 違う部分木なら操作は干渉しないので、部分木内での操作の順序を守れば順序を入れ替えることができる

AB

C

証明
X

Y・・・ １

１ ・・・

 𝐶を含む部分木の操作がすべて𝐴を含む部分木の操作の前になるように順序を入れ替える

A

B

C

証明
X

Y・・・ １

１ ・・・

 操作𝑋（とその前に連続する同じ人の移動のかたまり）と干渉するのは𝐴を含む部分木だけ
 操作𝑌と干渉するのは𝐶を含む部分木だけYX
ABC

証明・・・

X

１Y

１・・・

 順序を入れ替えて𝑋と𝑌のかたまりを連続させることができる

YX
ABC

証明・・・

X

１

Y

１・・・

 同じ人の操作は同じ部

分木に属するからこれらの入れ替えで連続した人が離れてしまうことはない

YX
ABC

証明・・・ ２

２

１

１

１４

４４ ・・・ これを繰り返すことで全員が自分の操作は連続するような操作列をつくることができる

より簡単な問題への帰着
 操作は次のようにしてもよい 人を1人選んでその人を初期地点から目的地点まで移動させる

 ただしその経路上に他の人がいてはならない

小課題３

 𝑄 ≤ 20，𝑁 ≤ 250，𝑀 ≤ 6
 𝑀が小さいので移動する順番を全探索できる 𝑂(𝑄𝑀! 𝑁)

考察 満たすべき条件「操作のとき移動する人の経路に他の人がいない」=条件「人𝑋の移動のときその経路上に人𝑌がいない」を（1 ≤ 𝑋 < 𝑌 ≤ 𝑀）ですべて満たす

考察 「人𝑋の移動のときその経路上に人𝑌がいない」
 人𝑌は初期地点𝑆𝑌 にいる（まだ移動していない）か目的地点𝑇𝑌にいる（移動を終えた）のどちらかである

考察
 「人𝑋の移動のときその経路上に人𝑌がいない」
 人𝑌は初期地点𝑆𝑌 にいる（まだ移動していない）か目的地点𝑇𝑌にいる（移動を終えた）のどちらかである

 人Xの経路上に𝑆𝑌 があるとき「人𝑌の移動は人𝑋の移動より先でなければならない」
 人𝑋の経路上に𝑇𝑌 があるとき「人𝑋の移動は人𝑌の移動より先でなければならない」

考察
 つまり順番について2つの順序がたくさん与えられるのでそれを満たす順番が存在するかを判定する問題となる

考察

 𝑀頂点のグラフを用意して、「𝑋が𝑌より先」という条件を𝑋から𝑌への有向辺であらわす

考察

 𝑀頂点のグラフを用意して、「𝑋が𝑌より先」という条件を𝑋から𝑌への有向辺であらわす

 すると条件を満たす順番が存在する⇔グラフに閉路がない
 閉路がないならトポロジカルソートをすることで実際に順番を構築できる小課題４

 𝑄 ≤ 20，𝑁 ≤ 250，𝑀 ≤ 100
 人𝑋, 𝑌の組を全探索して𝑋と𝑌の間の有向辺を調べる

小課題４

 𝑋の移動を考えた時𝑌との間に辺がはられる条件
 𝑆𝑋 – 𝑇𝑋 パス上に𝑆𝑌 がある(𝑋←𝑌の辺) 𝑆𝑋 – 𝑇𝑋 パス上に𝑇𝑌 がある(𝑌←𝑋の辺)
 𝑁が小さいのでパスを1つずつたどって判定しても間に合う 𝑂(𝑄𝑀 2 𝑁)

小課題５

 𝑄 ≤ 20，𝑀 ≤ 500
 人𝑋, 𝑌の組を全探索して𝑋と𝑌の間の有向辺を調べる 「𝐴-𝐵パス上に𝐶があるか」の判定を高速化する

小課題５
 根付き木にしてオイラーツアーをする
 すると「頂点𝑋が頂点𝑌の先祖か」を𝑂(1)で判定できる

 「𝐴-𝐵パス上に𝐶がある」＝「𝐿𝐶𝐴(𝐴, 𝐵)は𝐶の先祖かつ𝐶は𝐴の先祖」or 「𝐿𝐶𝐴(𝐴, 𝐵)は𝐶の先祖かつ𝐶は𝐵の先祖」

小課題５

 𝑀人それぞれのパスの𝐿𝐶𝐴をあらかじめ求めておくと判定が𝑂(1)でできる
 𝑂(𝑄(𝑀2 + 𝑀𝑙𝑜𝑔𝑁))

小課題６
 どの部屋からどの部屋へも，高々 20 本の通路を使って移動することができる．

 それぞれの人のパスも21頂点以下である

小課題６
 辺をはるのはパス上に𝑆または𝑇がある人のみ
 各頂点にそこに𝑆がある人の番号、𝑇がある人の番号を記録

 各人についてパスをたどってそこに書いてある番号の人と辺をはる小課題６
 根付き木にしてパスの𝐿𝐶𝐴を求めておくと端点から親へたどっていくことでパスだけみることができる 𝑂(𝑀𝑙𝑜𝑔𝑁 + 20𝑀)

満点

 𝑀人それぞれについてその経路上に有向辺をはる問題
 パスに対して辺をはる操作を高速に行いたい満点 有向辺をはるという操作は（閉路判定においては）最大値を求める操作と同じように前計算でいくつかのものをまとめておくとその計算結果が利用できる

満点

 例えば下の頂点の列について3 … 11に有向辺をはるとき

満点

 愚直にはると時間がかかるが満点

 前計算で4つずつまとめて有向辺をはった頂点を作っておくと満点

 その頂点（最大値でいうところの計算結果）を利用できる

３～１１

満点

 その頂点（最大値でいうところの計算結果）を利用できる

4~12

満点
 パス上に辺を高速にはりたい パス上の最大値を求める操作と同じようにできる ダブリングでできる！

満点

 𝐿𝐶𝐴をダブリングで求める手法を思い出してみよう 各頂点から20 回, 21 回, 22 回, … , 2𝑘 回先の祖先を計算している 同じように各頂点から根まで20 回, 21 回, 22 回, … , 2𝑘 回たどった

経路上にある頂点すべてに有向辺がはられた頂点を用意する

満点

 𝑘の小さい順に構築していく 𝑣から2𝑘 個に辺をはる頂点𝑒[𝑣][𝑘]からは𝑣から2𝑘−1 個に辺をはった頂点
𝑒[𝑣][𝑘 − 1]と𝑣の2𝑘−1 回先の頂点から2𝑘−1 個に辺をはった頂点𝑒[𝑝𝑎𝑟[𝑣][𝑘 − 1]][𝑘 − 1]の2つに辺をはれば構築できる満点

 𝑣 – 𝑢パスに有向辺をはるとき
 𝑣 – 𝐿𝐶𝐴(𝑣, 𝑢)と𝑢 – 𝐿𝐶𝐴(𝑣, 𝑢)にはるとして

満点

 𝑟 = 2𝑘 , 2𝑘−1 , 2𝑘−2 , … , 20 として𝑟個先を確認して𝐿𝐶𝐴以下ならそこから𝑟個に辺をはって(𝑒[𝑣][𝑟]に辺をはって)𝑟個先にいく(𝑣 = 𝑝𝑎𝑟[𝑣][𝑟])満点 できあがった(𝑁 + 𝑀)𝑙𝑜𝑔𝑁頂点のグラフで閉路判定をする
 𝑂((𝑁 + 𝑀)𝑙𝑜𝑔𝑁)で解ける

満点（別解） 根で分けたとき、𝑆と𝑇が違う部分木にあるものはもっと簡単に辺をはれる 𝑆から根まで、𝑇から根までに辺をはることになるが どちらも根まではるので、各頂点について根からの累積和のような頂点を用意しておけばよい（𝑣の累積頂点は親の累積頂点と𝑣に有向辺をはって構築）満点（別解） では𝑆 - 𝑇が同じ部分木にあるものは
 その部分木について再帰的に問題を解けばよい

 根として重心を選んでいくと再帰の深さが𝑙𝑜𝑔𝑁でおさまる（重心分解）

 𝑂((𝑁 + 𝑀)𝑙𝑜𝑔𝑁)

得点分布
 100点 5人
 77点 6人
 66点 3人
 54点 2人
 26点 4人

 10点 6人
 5点 1人
 0点 2人