ABC 376 G — Treasure Hunting

考察

宝を見つけるまでに調べる順序を決め、見つかるまでの回数を宝の位置の確率で重み付けする。親を先に調べる制約はあるが、重い子孫を早めるために親子を一続きの列へまとめると、列どうしの交換で最適な順序を決められる。

未発見の間の戦略を一本の順序へ表す

操作後に宝が見つかれば終了し、続ける場合に得る情報は「今の頂点にもなかった」だけである。したがって、決定的な戦略について、毎回未発見だった場合の次の選択をたどれば、全頂点を調べる一本の順序が定まる。逆に、その順序の途中で宝を見つけたら止めれば元の戦略を再現できる。乱択しても決定的な戦略の期待値の平均になるため、最小値を改善できない。

探索順を q1,…,qNq_1,\ldots,q_N とし、最初から探索済みの根を q0=0q_0=0 とする。合法な順序とは、各頂点よりもその親が先に現れる順序である。S=∑v=1NavS=\sum_{v=1}^N a_v とおくと、頂点 qiq_i に宝があればちょうど ii 回操作するので、期待値は

E(q)=1S∑i=1Ni aqiE(q)=\frac{1}{S}\sum_{i=1}^N i\,a_{q_i}

となる。SS は順序に依存せず正なので、まず整数の分子を最小化する。

親が探索済みの頂点から重み最大を選び続ける方法では、まだ選べない重い子孫を早める効果を評価できない。例えば p=(0,0,1), a=(1,5,100)p=(0,0,1),\ a=(1,5,100) では、最初に頂点2を選ぶと分子は 5+2+300=3075+2+300=307 だが、頂点1を先に調べて子3を解禁すれば、順序 (1,3,2)(1,3,2) の分子は 1+200+15=2161+200+15=216 になる。単頂点の重みから、親子をまとめた列の比較へ進みたい。

根の「1」で位置重み和を転倒数にする

各頂点 vv を「ava_v 個の0の後に1が一つある列」0av10^{a_v}1 とみなす。a0=0a_0=0 とし、根0にも列 1 を割り当てる。転倒数とは、1が0より前にある組の数である。根を含む列を q0,q1,…,qNq_0,q_1,\ldots,q_N の順につなぐと、頂点 qiq_i の各0より前には、根を含めてちょうど ii 個の1がある。よって全転倒数 II は

I=∑i=1Ni aqiI=\sum_{i=1}^N i\,a_{q_i}

に一致する。根は操作回数を消費しないが、その1は、最初に探索する頂点の位置を1にする役割を持つ。この規約なら、最後に定数を足し引きする必要はない。0を実際に並べる必要もなく、個数だけ持てばよい。

内部順序を固定した頂点列をブロックと呼ぶ。ブロック BB には、0の個数 C0(B)C_0(B)、1の個数 C1(B)C_1(B)、内部転倒数 I(B)I(B) を持たせる。初期値は、根を含む全頂点について

(C0(v),C1(v),I(v))=(av,1,0)(C_0(v),C_1(v),I(v))=(a_v,1,0)

である。C0C_0 は重み総和、C1C_1 は根も数える頂点数になる。

AA の後に BB をつなぐと、境界をまたぐ転倒は AA の1と BB の0の組だから、

I(AB)=I(A)+I(B)+C1(A)C0(B)I(AB)=I(A)+I(B)+C_1(A)C_0(B)

となる。従って、互いに前後を交換できる二ブロックについて ABAB が BABA 以下の費用となる条件は

C0(A)C1(B)≥C0(B)C1(A)C_0(A)C_1(B)\geq C_0(B)C_1(A)

であり、C0/C1C_0/C_1 の大きい方を先にしたい。この比率は「列全体の1個の頂点当たりの重み」を表す。

非根ブロックのうち比率最大のものを BB、その現在の親ブロックを PP とする。PP と BB の間のブロックを越えて BB を左へ移すと、親先行制約を保ち、上の比較により費用も増えない。そのため、PP の直後に BB がある最適順序を選べる。内部順を PBPB に固定して一ブロックへ縮約し、比率を計算し直せばよい。交換と縮約の詳しい対応は単元の交換論を参照する。

縮約から期待値の出力まで

次の操作は、探索順の先頭から一頂点ずつ確定するものではなく、最適順序で隣接してよい列をまとめる操作である。

  1. 根以外の NN ブロックを、C0/C1C_0/C_1 が最大のものを取り出す heap に入れる。比率は除算せず交差積で比較し、同率ならどちらを選んでもよい。
  2. 有効な最大ブロック BB を取り出し、その先頭頂点の元の親が属する現在のブロック PP をDSUで求める。先頭以外の頂点の親はブロック内部にあるため、外から入る親辺はこれで特定できる。
  3. PP の末尾に BB をつなぐ。結合前の統計を用いて Inew=I(P)+I(B)+C1(P)C0(B)I_{\mathrm{new}}=I(P)+I(B)+C_1(P)C_0(B) とし、C0,C1C_0,C_1 はそれぞれ加算する。DSUで成分を併合し、新ブロックの先頭は PP の先頭を引き継ぐ。
  4. 更新したブロックが根0を含まなければ、新しい統計で heap へ入れ直す。根を含むブロックは他へ結合する対象にならないので入れない。古い要素の無効化は「実装上の注意」の方法で行う。

N+1N+1 ブロックから NN 回の有効な結合を行うと、根を含む一ブロックになる。その内部転倒数を I∗I_* とすれば、最小期待値は I∗/SI_*/S である。必要なのは値なので、頂点列そのものを復元せず、上の統計だけで足りる。

例えば N=2, p=(0,1), a=(1,3)N=2,\ p=(0,1),\ a=(1,3) では、頂点2を1へ結合して内部転倒数は 0+0+1×3=30+0+1\times3=3、統計は (C0,C1)=(4,2)(C_0,C_1)=(4,2) となる。これを根へつなぐと I∗=0+3+1×4=7I_*=0+3+1\times4=7。列は 1 01 0001 で、根の1も転倒に寄与している。S=4S=4 なので期待値は 7/47/4 である。

出力は実数や整数の除算ではなく、法 M=998244353M=998244353 における

(I∗ mod M) SM−2 mod M(I_*\bmod M)\,S^{M-2}\bmod M

を各テストケースに一つずつ出す。MM は素数で、制約より 1≤S≤108<M1\leq S\leq10^8<M だから逆元が存在する。上の例の出力は 249561090249561090 になる。最適順序の比較は整数で済ませ、法上の計算は最後の期待値の回収に使う。

典型の発動条件

01 on Tree

親が子より先という木の順序制約があり、二つの固定列を連結したときの追加費用を、各列の0と1の個数の積で表せるときに使う。交換比較で最優先の非根ブロックを親直後へ寄せ、内部順を固定して縮約する。一般のDAGでは、移動先までに別の先行条件を壊すことがあり、この交換をそのまま使えない。

問題固有の要素

探索を続ける際の観測が未発見の一種類しかないことから、適応的な戦略を一本の順序へ表せる点が出発点になる。位置と重みの積を見たら、その位置を「前にある要素の個数」として数え直す。今回は探索済みの根に置く1が、操作回数の1始まりと転倒数を一致させる。

正当性

未発見の場合の選択をたどることで、決定的な戦略と合法な親先行順序が対応する。乱択戦略はその平均なので、合法順序の最小期待値を下回らない。根0を列 1 として含めると、位置 ii の頂点の各0には先行する1がちょうど ii 個あり、全転倒数は期待値の分子に一致する。

現在の非根ブロックで比率最大のものを BB、親を PP とする。合法順序で両者の間にあるブロックは BB の祖先でも子孫でもなく、BB を PP の直後まで左へ移しても合法である。交換する各ブロックより BB の比率が大きいか等しいため、費用は増えない。従って内部順 PBPB を固定する最適解が存在し、その縮約後の問題にも同じ議論を適用できる。

各初期列の内部転倒数は0であり、結合式は両列の内部転倒と境界をまたぐ転倒を重複なく数える。よって NN 回の結合で得る I∗I_* は最小の分子そのものである。最後に正の定数 SS で割れば最小期待値となり、出力は問題で指定された法上の除算により I∗S−1 mod 998244353I_*S^{-1}\bmod998244353 として回収できる。

実装上の注意

  • DSUの代表番号は、サイズによる併合で変わり得る。各代表にブロック先頭 head と統計を保存し、現在親は find(p[head]) で求める。併合前に親側の先頭と両側の統計を取り出し、併合後の代表へ書き戻す。代表番号を列の先頭や親だとみなさない。根を含むかは先頭が0かで判定できる。
  • heapには、挿入時の代表番号・版番号・C0,C1C_0,C_1 の値の組を保存する。比較時に可変の統計配列を参照すると、heap内の順序が更新されず壊れる。取り出した代表が既に代表でない、版が現在値と違う、または根を含む場合は捨てる。結合後の代表の版を必ず増やして統計を書き戻し、非根なら新要素を挿入する。これで親側に残る旧要素も無効になる。
  • 比率が同じ場合は代表番号などで順序を揃えてよい。C1≥1C_1\geq1 なので分母0はない。根を初期heapから除外し、以後も根を含むブロックを再挿入しない。
  • C0≤SC_0\leq S、C1≤N+1C_1\leq N+1 であり、交差積は S(N+1)S(N+1) 以下、転倒数は NSNS 以下である。最大でも約 2×10132\times10^{13} なので符号付き64 bit整数で保持できる。積は乗算前に64 bitへ拡張し、比率比較用の値を法で丸めない。
  • N=1N=1 でも根との一回の結合が必要で、I∗=S=a1I_*=S=a_1 から出力1を得る。一直線の木も、全頂点が根の子である木も同じ手順で扱える。後者では重みの大きい順となる。テストケースごとにDSU・統計・版・heapを初期化する。

復習の核

  • 未発見なら続行、発見なら終了、という観測なら、未発見時の選択をたどって一本の探索順へ落とせる。
  • 位置重み和を転倒数へ変換するときは、先行する1の個数を数える。今回の根の1を含む規約では補正は不要である。
  • 頂点の優先度ではなく、結合後の列全体の比率を更新する。最優先ブロックを親直後へ寄せられることが縮約の根拠になる。

計算量と制約

時間

1ケース当たり、入力とDSU・統計の初期化は O(N)O(N)。有効な結合は NN 回で、heapへの追加と古い要素の取り出しも合計 O(N)O(N) 回だから O(Nlog⁡(N+1))O(N\log(N+1))、サイズによる併合と経路圧縮を使うDSUは合計 O(Nα(N))O(N\alpha(N))。逆元を繰り返し二乗法で求める O(log⁡M)O(\log M) を含め、全体は O(Nlog⁡(N+1)+log⁡M)O(N\log(N+1)+\log M)。全ケースではこれらの和となる。

空間

入力の親・重み、DSUと各ブロックの先頭・統計・版番号、合計 O(N)O(N) 個のheap要素を持ち、1ケース当たり O(N)O(N)。01列や探索順を展開しない。

制約との対応

1≤T≤2×1051\leq T\leq2\times10^5、1≤N≤2×1051\leq N\leq2\times10^5、0≤pi<i0\leq p_i<i、ai≥1a_i\geq1、S=∑i=1Nai≤108S=\sum_{i=1}^N a_i\leq10^8。全ケースの NN の総和は 2×1052\times10^5 以下である。各ケースの処理を頂点数に対してほぼ線形に抑え、重み総和に比例する01列の展開を避ける。S<MS<M により法上の逆元も必ず存在する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Treasure Hunting の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 01 on Tree・親先行順序のcluster縮約

主題
追加で学ぶ技能
    なし
    既習技能
    • priority queue・best-first列挙: 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
    • DSUによる連結成分管理・縮約: 静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。
    • 交換論から選択順を導く: 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

    主タグ: 01 on Tree・親先行順序のcluster縮約

    補助タグ: DSUによる連結成分管理・縮約 貪欲法と交換論 priority queue・best-first列挙

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 01 on Tree・親先行順序のcluster縮約

    • 親先行制約下の交換比較をcluster統計へまとめ、01 on Treeの縮約貪欲で最適順序を構成できる。

    先に読む単元:

    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • 交換論から選択順を導く — 局所選択を交換論で正当化し、候補を安全に確定できる順序を導く。
    • priority queue・best-first列挙 — 現在のfrontierの極値をheapで確定し、新しく解禁された候補だけを追加して上位K個や最良状態を列挙する。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題