考察
宝を見つけるまでに調べる順序を決め、見つかるまでの回数を宝の位置の確率で重み付けする。親を先に調べる制約はあるが、重い子孫を早めるために親子を一続きの列へまとめると、列どうしの交換で最適な順序を決められる。
未発見の間の戦略を一本の順序へ表す
操作後に宝が見つかれば終了し、続ける場合に得る情報は「今の頂点にもなかった」だけである。したがって、決定的な戦略について、毎回未発見だった場合の次の選択をたどれば、全頂点を調べる一本の順序が定まる。逆に、その順序の途中で宝を見つけたら止めれば元の戦略を再現できる。乱択しても決定的な戦略の期待値の平均になるため、最小値を改善できない。
探索順を とし、最初から探索済みの根を とする。合法な順序とは、各頂点よりもその親が先に現れる順序である。 とおくと、頂点 に宝があればちょうど 回操作するので、期待値は
となる。 は順序に依存せず正なので、まず整数の分子を最小化する。
親が探索済みの頂点から重み最大を選び続ける方法では、まだ選べない重い子孫を早める効果を評価できない。例えば では、最初に頂点2を選ぶと分子は だが、頂点1を先に調べて子3を解禁すれば、順序 の分子は になる。単頂点の重みから、親子をまとめた列の比較へ進みたい。
根の「1」で位置重み和を転倒数にする
各頂点 を「 個の0の後に1が一つある列」 とみなす。 とし、根0にも列 1 を割り当てる。転倒数とは、1が0より前にある組の数である。根を含む列を の順につなぐと、頂点 の各0より前には、根を含めてちょうど 個の1がある。よって全転倒数 は
に一致する。根は操作回数を消費しないが、その1は、最初に探索する頂点の位置を1にする役割を持つ。この規約なら、最後に定数を足し引きする必要はない。0を実際に並べる必要もなく、個数だけ持てばよい。
内部順序を固定した頂点列をブロックと呼ぶ。ブロック には、0の個数 、1の個数 、内部転倒数 を持たせる。初期値は、根を含む全頂点について
である。 は重み総和、 は根も数える頂点数になる。
の後に をつなぐと、境界をまたぐ転倒は の1と の0の組だから、
となる。従って、互いに前後を交換できる二ブロックについて が 以下の費用となる条件は
であり、 の大きい方を先にしたい。この比率は「列全体の1個の頂点当たりの重み」を表す。
非根ブロックのうち比率最大のものを 、その現在の親ブロックを とする。 と の間のブロックを越えて を左へ移すと、親先行制約を保ち、上の比較により費用も増えない。そのため、 の直後に がある最適順序を選べる。内部順を に固定して一ブロックへ縮約し、比率を計算し直せばよい。交換と縮約の詳しい対応は単元の交換論を参照する。
縮約から期待値の出力まで
次の操作は、探索順の先頭から一頂点ずつ確定するものではなく、最適順序で隣接してよい列をまとめる操作である。
- 根以外の ブロックを、 が最大のものを取り出す heap に入れる。比率は除算せず交差積で比較し、同率ならどちらを選んでもよい。
- 有効な最大ブロック を取り出し、その先頭頂点の元の親が属する現在のブロック をDSUで求める。先頭以外の頂点の親はブロック内部にあるため、外から入る親辺はこれで特定できる。
- の末尾に をつなぐ。結合前の統計を用いて とし、 はそれぞれ加算する。DSUで成分を併合し、新ブロックの先頭は の先頭を引き継ぐ。
- 更新したブロックが根0を含まなければ、新しい統計で heap へ入れ直す。根を含むブロックは他へ結合する対象にならないので入れない。古い要素の無効化は「実装上の注意」の方法で行う。
ブロックから 回の有効な結合を行うと、根を含む一ブロックになる。その内部転倒数を とすれば、最小期待値は である。必要なのは値なので、頂点列そのものを復元せず、上の統計だけで足りる。
例えば では、頂点2を1へ結合して内部転倒数は 、統計は となる。これを根へつなぐと 。列は 1 01 0001 で、根の1も転倒に寄与している。 なので期待値は である。
出力は実数や整数の除算ではなく、法 における
を各テストケースに一つずつ出す。 は素数で、制約より だから逆元が存在する。上の例の出力は になる。最適順序の比較は整数で済ませ、法上の計算は最後の期待値の回収に使う。
典型の発動条件
01 on Tree
親が子より先という木の順序制約があり、二つの固定列を連結したときの追加費用を、各列の0と1の個数の積で表せるときに使う。交換比較で最優先の非根ブロックを親直後へ寄せ、内部順を固定して縮約する。一般のDAGでは、移動先までに別の先行条件を壊すことがあり、この交換をそのまま使えない。
問題固有の要素
探索を続ける際の観測が未発見の一種類しかないことから、適応的な戦略を一本の順序へ表せる点が出発点になる。位置と重みの積を見たら、その位置を「前にある要素の個数」として数え直す。今回は探索済みの根に置く1が、操作回数の1始まりと転倒数を一致させる。
正当性
未発見の場合の選択をたどることで、決定的な戦略と合法な親先行順序が対応する。乱択戦略はその平均なので、合法順序の最小期待値を下回らない。根0を列 1 として含めると、位置 の頂点の各0には先行する1がちょうど 個あり、全転倒数は期待値の分子に一致する。
現在の非根ブロックで比率最大のものを 、親を とする。合法順序で両者の間にあるブロックは の祖先でも子孫でもなく、 を の直後まで左へ移しても合法である。交換する各ブロックより の比率が大きいか等しいため、費用は増えない。従って内部順 を固定する最適解が存在し、その縮約後の問題にも同じ議論を適用できる。
各初期列の内部転倒数は0であり、結合式は両列の内部転倒と境界をまたぐ転倒を重複なく数える。よって 回の結合で得る は最小の分子そのものである。最後に正の定数 で割れば最小期待値となり、出力は問題で指定された法上の除算により として回収できる。
実装上の注意
- DSUの代表番号は、サイズによる併合で変わり得る。各代表にブロック先頭
head と統計を保存し、現在親は find(p[head]) で求める。併合前に親側の先頭と両側の統計を取り出し、併合後の代表へ書き戻す。代表番号を列の先頭や親だとみなさない。根を含むかは先頭が0かで判定できる。
- heapには、挿入時の代表番号・版番号・ の値の組を保存する。比較時に可変の統計配列を参照すると、heap内の順序が更新されず壊れる。取り出した代表が既に代表でない、版が現在値と違う、または根を含む場合は捨てる。結合後の代表の版を必ず増やして統計を書き戻し、非根なら新要素を挿入する。これで親側に残る旧要素も無効になる。
- 比率が同じ場合は代表番号などで順序を揃えてよい。 なので分母0はない。根を初期heapから除外し、以後も根を含むブロックを再挿入しない。
- 、 であり、交差積は 以下、転倒数は 以下である。最大でも約 なので符号付き64 bit整数で保持できる。積は乗算前に64 bitへ拡張し、比率比較用の値を法で丸めない。
- でも根との一回の結合が必要で、 から出力1を得る。一直線の木も、全頂点が根の子である木も同じ手順で扱える。後者では重みの大きい順となる。テストケースごとにDSU・統計・版・heapを初期化する。
復習の核
- 未発見なら続行、発見なら終了、という観測なら、未発見時の選択をたどって一本の探索順へ落とせる。
- 位置重み和を転倒数へ変換するときは、先行する1の個数を数える。今回の根の1を含む規約では補正は不要である。
- 頂点の優先度ではなく、結合後の列全体の比率を更新する。最優先ブロックを親直後へ寄せられることが縮約の根拠になる。
計算量と制約
時間
1ケース当たり、入力とDSU・統計の初期化は 。有効な結合は 回で、heapへの追加と古い要素の取り出しも合計 回だから 、サイズによる併合と経路圧縮を使うDSUは合計 。逆元を繰り返し二乗法で求める を含め、全体は 。全ケースではこれらの和となる。
空間
入力の親・重み、DSUと各ブロックの先頭・統計・版番号、合計 個のheap要素を持ち、1ケース当たり 。01列や探索順を展開しない。
制約との対応
、、、、。全ケースの の総和は 以下である。各ケースの処理を頂点数に対してほぼ線形に抑え、重み総和に比例する01列の展開を避ける。 により法上の逆元も必ず存在する。
出典