ABC 451 G — Minimum XOR Walk

考察

無向連結graphの全域木を一つ選び、根からvまでの辺ラベルXORをA_vとする。辺e=(u,v)についてW'_e=W_e XOR A_u XOR A_vを作る。木辺なら0、非木辺なら基本閉路のラベルXORとなる。

任意のs→t walkでは、各辺W_e=W'_e XOR A_u XOR A_vと展開すると、中間頂点のAが二回ずつ消え、walk XOR=A_s XOR A_t XOR(通ったW'_eのXOR)となる。従って可能値はA_s XOR A_tのcycleラベルspan Vによるcosetへ含まれる。逆に任意の非木辺eの基本閉路へsから木経路で往復すると、接続部分は二回通ってXORが消え、W'_eだけを加えられる。この閉じた寄り道を必要な辺ごとに挿入してからs→tの木経路を進めば、span Vの任意要素を実現できる。walkが無限個あることと、ラベルの可能値が有限のspanであることを区別する。

Vの最高bit基底でcosetの最小代表f(x)を求める。bit bが1ならpivot行basis[b]をXORして0にする、高bit順の消去を用いる。一段はx→x XOR (x_b·basis[b])というF₂線形写像なので、その合成fも線形である。消去後の非零なV要素は最上位pivotで0→1を作るから、f(x)がcosetの最小となる。よって二点の最小walk XORはf(A_s XOR A_t)=f(A_s) XOR f(A_t)となり、各頂点をB_v=f(A_v)へ一回だけ正規化すればよい。既約基底を作って全pivot列を消す方法でも同じ最小代表を得る。

Bを一つずつbinary trieへ挿入し、それ以前のyでB XOR y≤Kとなる個数を数える。問い合わせ時に同じprefixのnodeを高bitから追い、x=Bのbitとする。Kのbitが0ならyのbitをxと同じにして継続。Kのbitが1ならyのbitがxと同じ子の全個数を加え(このbitでK未満になる)、逆の子へ継続して一致を保つ。全bitを処理した後は一致nodeの個数も加えて等号を含める。必要な子がなければ継続を終了する。

queryしてからBを挿入するので、相異なるunordered頂点pairを一度ずつ数え、自己pairを入れない。同じBを持つ異なる頂点はそれぞれ頻度として残す。

典型の発動条件

cycle xor の線形基底

発動条件: graph walk に cycle を挿入して xor 重みを最小化・可否判定するとき。

spanning tree potential で辺を cycle xorへ変換し span を作る。

binary trie の xor pair 数え上げ

発動条件: 多数の値 pair で xor が閾値以下となる個数を求めたいとき。

K のbitに従い枝ごとの個数を一括加算する。

問題固有の要素

graph の xor walk は tree potential で端点依存部分と cycle span に分離できる。

別の問題へ持ち帰る視点: pair ごとの coset 最小化が各値の canonical 化へ分離できるかは、正規化写像の xor 線形性を証明して判断する。

正当性

辺ラベルをW_e=W'_e XOR A_u XOR A_vと展開すると、任意のs→t walkのXORはA_s XOR A_tにW'_eの線形結合を足した値となる。各基本閉路を木経路の往復で接続した寄り道により任意の線形結合も実現できるから、可能集合はそのcoset全体である。

高位pivotの消去は各段が線形写像で、全pivotを0にした代表は非零のspan要素を足すと最上位pivotが1になり増える。従ってfは線形な最小代表写像であり、最小walk XOR=f(A_s) XOR f(A_t)。trieのK=1のbitで加える枝はそこで初めてK未満になる値、追う枝はprefix一致の値を数える。最後の一致も加えて≤Kを正確に判定する。queryを挿入前に行えば相異なるunordered pairだけを一度数える。

実装上の注意

  • 全域木とcycleラベルspanはこの連結graph内で作る。高bitからpivot bitを0にする一定の消去順で全A_vを正規化する。最小代表には既約化は必須ではなく、単なる最高bit基底でもこの順序なら同じ写像になる。
  • trieはnodeごとの通過頻度を持ち、query後に挿入する。K=0や同じ正規化値の複数頂点も含める。pair総数は64bitで扱う。

復習の核

  • W'_e の telescoping 式、span の任意組合せを実現する walk、f(x⊕y) の線形性の三段を順に再構成する。

計算量と制約

時間

O((N+M)B+B²)、B=30。cycle基底とbinary trie。

空間

O(NB+M)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 10^5; 2 \leq N \leq 2 \times 10^5; N-1 \leq M \leq 2 \times 10^5; 0 \leq K \lt 2^{30}; 1 \leq U_i \lt V_i \leq N; 0 \leq W_i \lt 2^{30}; The given graph is simple and connected.; All input values are integers.; The sum of N over all test cases in a single input is at most 2 \times 10^5.; The sum of M over all test cases in a single input is at most 2 \times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Minimum XOR Walk の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: XOR線形基底

主題
  • XOR線形基底: XOR部分空間の基底をpivot bitごとにreduced formへ整え、高位bitから基底を加減してaffine cosetの最小整数代表を一意に得る。正規化写像の線形性を示し、二値のXOR最小化を各値の正規化へ分離できる。
追加で学ぶ技能
    なし
    既習技能
    • cycle space・fundamental cycle basis: spanning treeのroot-to-vertex XOR potentialで辺ラベルをfundamental cycleのXORへ変換し、cycle spaceの線形像が非木辺ごとのcycle XORのspanと一致することを示して、walkへ挿入できるXOR値をbasisで表せる。
    • bit列をTrieで索引化する: 整数を上位bitからTrieへ格納し、部分木情報を保ちながらXOR・大小条件に最適な分岐を選べる。

    主タグ: XOR線形基底

    補助タグ: binary Trieによるbit列索引 cycle space・fundamental cycle basis

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

    学習の位置

    体系上の位置: XOR線形基底

    • XOR部分空間の基底をpivot bitごとにreduced formへ整え、高位bitから基底を加減してaffine cosetの最小整数代表を一意に得る。正規化写像の線形性を示し、二値のXOR最小化を各値の正規化へ分離できる。

    先に読む単元:

    • bit列をTrieで索引化する — 整数を上位bitから分岐する列として格納し、XOR・大小・最小距離の候補を貪欲に選ぶ。
    • cycle space・fundamental cycle basis — 無向graphを探索してspanning forestを構築できることを土台に、偶数次数辺集合をF_2上のcycle spaceとして捉え、fundamental cycle basisとdim C(G)=M-N+C(Cは連結成分数)を導く。さらに辺labelによる線形写像を通してcycle XORのspanを作り、path族の上界やwalk XORの自由度へ接続する。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題