ABC 366 G — XOR Neighbors

考察

各bitについて頂点値vector xを考えると、全頂点で隣接値XORが0という条件はGF(2)上の隣接行列Aに対するAx=0である。

各頂点へ非零整数を置くには、選んだkernel vector群のbitwise ORが全座標を覆えばよい。kernel基底で覆えない座標はkernelのどのvectorでも1にできない。

採用する候補: 隣接行列をGF(2)で掃き出してkernel基底を求め、基底indexを出力整数のbitへ割り当てる。

各bit vectorが条件式を満たし、基底のORによる座標被覆が非零条件の必要十分判定になる。

棄却する候補: 各頂点へ非零整数を順に割り当て、隣接XOR条件を後から局所修正する。

一頂点の変更が全隣接式へ同時に影響し、局所選択では連立一次制約を保てない。

kernelはXORで閉じるvector spaceなので、基底に現れない座標は全解で0、どれかの基底に現れる座標は対応bitで非零化できる。

N≤60なら各rowとvectorを64 bit maskにし、pivot消去でrank・free変数・kernel基底を構成できる。

隣接行列の各rowをbit maskにしてGF(2) Gaussian eliminationを行う。各free変数を1としたkernel基底vectorを復元し、そのORが全N bitを覆わなければNo。覆うなら基底b_kごとに、b_kの頂点i成分が1ならanswer_iのk bitを立て、Yesと全answerを出力する。

典型の発動条件

GF(2) nullspace構成

発動条件: XORによる線形条件を同時に満たすassignmentが必要なとき。

係数行列をbitset掃き出しし、free変数からkernel基底を得る。

基底vectorのbit packing

発動条件: 複数の0/1解を各要素の非零性を満たす整数へまとめたいとき。

解vectorごとに別の出力bitを割り当て、各座標の列を整数化する。

問題固有の要素

頂点値を直接未知数にせず、整数の各bitを独立なkernel解と見れば、XOR条件と非零条件を分離できる。

別の問題へ持ち帰る視点: bitwise制約ではbit planeごとの線形解を作り、最後に列方向へpackingする。

正当性

各bitの隣接XOR条件はAx=0であり、全合法bit列はkernel。どのkernel基底でもcoordinate iが全基底で0なら全kernelで0となり頂点iへ非零を置けない。逆に各coordinateがある基底で1なら基底番号を異なるbitとして重ねれば全頂点非零で、各bitがkernelなので全隣接XORも0。OR被覆条件は必要十分。

実装上の注意

  • 自己loopなしでも行列対角を勝手に立てない。N=60のmask shiftと出力上限2^N未満をunsigned 64 bitで安全に扱う。

復習の核

  • 得た各basisについてAx=0を再計算し、全answer_iが非零かassertする。free変数からpivot変数を復元する向きを固定する。

計算量と制約

時間

O(N³/w+N²)、w=64。bitmask消去とkernel基底復元。

空間

O(N²/w+N²)。出力値もN個。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 60; 0 \leq M \leq N(N-1)/2; 1 \leq u_i < v_i \leq N; (u_i, v_i) \neq (u_j, v_j) for i \neq j.; All input values are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 線形方程式・rank

主題
  • 線形方程式・rank: 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 線形方程式・rank

    補助タグ: bitsetによるword並列集合演算 構成解・witness復元

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

    学習の位置

    体系上の位置: 線形方程式・rank

    • 制約を体上の連立一次方程式へ写し、Gaussian eliminationでrank・可解性・解空間次元を求める。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題