ABC 396 E — Min of Restricted Sum

考察

辺で結ばれた二頂点では、片方の値を決めるとXORの条件からもう片方も決まる。そこで、まず一頂点を仮に0にして、成分内の相対的な値を求める。まだ自由に選べる根の値を後から調整すれば、制約を壊さずに総和を小さくできる。

入力の制約 AXi⊕AYi=ZiA_{X_i}\oplus A_{Y_i}=Z_i を、頂点 Xi,YiX_i,Y_i を結ぶ重み ZiZ_i の無向辺として表す。⊕\oplus はビットごとの排他的論理和(XOR)である。辺 u,vu,v の重みを zz とすると、Av=Au⊕zA_v=A_u\oplus z と書ける。逆向きも同じ重みでよい。辺のない別の連結成分とは制約を共有しないため、成分ごとに解いてよい。

根を0にして相対値を求める

一つの成分の根を rr とし、pr=0p_r=0 からDFS・BFSで仮の値 pvp_v を付ける。辺 u,vu,v を通るとき、未訪問なら pv=pu⊕zp_v=p_u\oplus z として記録する。訪問済みなら同じ等式を満たすか照合する。値が異なれば、二経路のXORが一致せず、どんな根の値でも解は存在しない。

矛盾がなければ、その成分の全解は共通のXORマスク tt により

Av=pv⊕tA_v=p_v\oplus t

と表せる。根では Ar=tA_r=t であり、tt が実際に選ぶ根の値になる。詳しい伝播と自由度の考え方は静的ポテンシャルの単元で確認できる。

根を0として探索することは、最適解の根も0と決めることではない。独自例として、制約が A1⊕A2=1A_1\oplus A_2=1、A2⊕A3=0A_2\oplus A_3=0 の三頂点を考える。根を頂点1とすると p=(0,1,1)p=(0,1,1) で、t=0t=0 のままでは総和は2になる。しかし t=1t=1 を共通にXORすると A=(1,0,0)A=(1,0,0) となり、二つの制約を満たしたまま総和を1へ減らせる。根だけを小さくしても、他の頂点を含む総和は最小にならない。

各bitで1の多い側を反転する

残った候補は tt の値だが、全整数を試す必要はない。XORではbit間に繰り上がりがなく、制約も目的の総和もbitごとに分けられる。

成分 CC の頂点数を ss、pvp_v のbit bb が1である頂点数を cbc_b とする。bitは最下位を0番とし、tbt_b を tt のbit bb と呼ぶ。tb=0t_b=0 なら1の個数は cbc_b のまま、tb=1t_b=1 なら全頂点のそのbitが反転して s−cbs-c_b 個になる。総和への寄与はそれぞれ

2bcb,2b(s−cb)2^b c_b,\qquad 2^b(s-c_b)

なので、cb>s−cbc_b>s-c_b のときだけ tb=1t_b=1 とすればよい。同数ならどちらでも最小になり、ここでは tb=0t_b=0 を選ぶ。先ほどの p=(0,1,1)p=(0,1,1) ではbit 0の1が2個、0が1個なので反転する。このように各bitで選んだ値を一つの tt にまとめられるため、成分の最小総和は

∑b≥02bmin⁡(cb,s−cb)\sum_{b\geq0}2^b\min(c_b,s-c_b)

となる。ただし求める出力はこの総和ではなく、最小化する数列 AA そのものである。

伝播・最小化・出力の手順

  1. 各制約を同じ重みの二方向の辺として保存し、全頂点を未訪問にする。
  2. 未訪問の根に pr=0p_r=0 を置き、スタックまたはキューで探索する。値を割り当てた時点で訪問済みにし、その成分の頂点一覧を集める。既訪問の頂点への辺も照合し、不一致があれば -1 を出力して終了する。
  3. 成分の頂点一覧を使って各bitの cbc_b を数え、上の比較から tt を作る。各頂点に Av=pv⊕tA_v=p_v\oplus t を格納する。
  4. 全成分を処理できたら、頂点番号順に A1,…,ANA_1,\ldots,A_N を空白区切りで出力する。

Zi≤109<230Z_i\leq10^9<2^{30} なので、伝播で得られる pvp_v のbit 30以上は全て0である。その上位bitを tt に立てると成分の全頂点に同じ正の寄与を足すだけなので、最適解でも0にできる。従って調べるのはbit 0から29までで十分である。

典型の発動条件

xor potential graph

辺が二頂点の値のXORを指定し、一方を決めると他方も一意に決まるとき、根からXORを累積して相対値を求める。別経路との照合で整合性を判定し、全解を成分共通のXORマスク一つに絞る。

bitwise independent minimization

制約がbit間で干渉せず、目的が各bitの寄与の和であるときに使う。本問では共通マスクの一つのbitが成分全体の反転を選ぶので、bitごとに1の個数の少ない方を選べる。整数の大小だけで一頂点ずつ貪欲に決めると、他頂点へ伝わる反転の影響を評価できない。

問題固有の要素

自由に選べるのは各頂点の値ではなく、成分共通のマスクだけである。本問はその各bitを独立に選べ、同じbitが1である各頂点の寄与も等しく 2b2^b なので、個数の比較だけで最小化できる。

別の問題へ持ち帰る視点: まず辺の等式から相対値を確定し、成分に残る自由度を取り出す。その自由度をbitごとに独立に最適化できるかは、制約と目的の両方から確認する。

正当性

根を0として得た相対値を pvp_v とする。全辺で pu⊕pv=zp_u\oplus p_v=z が成り立つなら、任意の共通マスク tt に対する Av=pv⊕tA_v=p_v\oplus t も、辺のXORで二つの tt が打ち消されるので全制約を満たす。逆に、任意の解で根の値を tt とすると、根からの経路に沿って Av=pv⊕tA_v=p_v\oplus t が強制されるので、これで全解を尽くす。照合に失敗した辺では、この形のどの候補も等式を満たせないため、解は存在しない。

成分の頂点数を ss、相対値のbit bb が1の頂点数を cbc_b とする。共通マスクのbitを0にした場合と1にした場合の総和への寄与は、それぞれ 2bcb2^b c_b と 2b(s−cb)2^b(s-c_b) である。制約はbit間・成分間で独立で、総和もその寄与の和なので、各々で小さい方を選ぶと全体の総和も最小になる。同数ならどちらを選んでも最小値は変わらない。全ての pvp_v で0となるbit 30以上は、共通マスクでも0にするのが最小である。

実装上の注意

  • 自己ループも照合する。Av⊕Av=0A_v\oplus A_v=0 なので、重みが0なら許され、非零なら -1 になる。同じ二頂点の多重辺も省略せず照合する。
  • 訪問状態は値0と区別し、割当て時に記録する。N≤2×105N\leq2\times10^5 なので、再帰の深さを避けたい場合は明示的なスタックやキューを使う。
  • 孤立点は s=1,pv=0s=1,p_v=0 なので t=0,Av=0t=0,A_v=0 が最小になる。M=0M=0 の場合は全頂点が孤立し、全要素0を出力する。
  • 最小化にはbitごとの個数だけが必要で、総和を計算する必要はない。検算などで総和を持つなら、N(230−1)N(2^{30}-1) まで収まる64 bit整数型を使う。

復習の核

  • 根を0に置くのは相対値を求めるため。総和最小の解は、成分全体への共通XORを選んで復元する。
  • XOR制約の自由度は成分ごとのマスク一つ。その各bitを変えると全頂点が反転するため、目的が総和なら1の多い側を反転する。
  • 閉路XORが非零なら、根の値の選び直しでは直せない矛盾である。

計算量と制約

時間

NN 頂点、MM 制約、調べるbit数を BB とする。隣接リスト構築と全成分の探索は O(N+M)O(N+M)。成分の頂点数を ss とすると各bitの個数集計は O(sB)O(sB) であり、全成分を合わせて O(NB)O(NB)。回答の復元・出力も含め、全体で O(N+M+NB)O(N+M+NB) 時間。

空間

隣接リスト、訪問状態、相対値、成分の頂点一覧、回答を保持する。bitは順に処理し、個数の作業領域を再利用できるので、全体で O(N+M)O(N+M) 空間。

制約との対応

1≤N≤2×1051\leq N\leq2\times10^5、0≤M≤1050\leq M\leq10^5、1≤Xi,Yi≤N1\leq X_i,Y_i\leq N、0≤Zi≤1090\leq Z_i\leq10^9。B=30B=30 とすれば各頂点につき30 bitを調べるだけでよく、全整数の根の値を列挙せずに処理できる。制限は3秒・1024 MiB。全ての入力は整数であり、孤立点・自己ループ・多重辺を含めて上の手順で扱える。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Min of Restricted Sum の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 静的graph等式制約のpotential伝播

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 静的graph等式制約のpotential伝播

    補助タグ: 構成解・witness復元

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

    学習の位置

    体系上の位置: 静的graph等式制約のpotential伝播

    • 辺等式をDFS/BFSでroot-relative potentialへ伝播し、cycle矛盾を検出して各連結成分の全解を自由offset一つで表現・復元できる。

    先に読む単元:

    • 成立証明から構成解を復元する — 存在条件の証明に対応する親・選択・局所操作を記録し、実際の構成へ戻す。
    • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題