XOR閾値matchingのbit分割再帰
固定閾値xに対し、XORがx以上となる最大pair数を求める。最上位bitで集合を分け、閾値bitが0なら確定できるcross pairを最大化し、1ならcross pairだけを残し、同一集合内と二集合間の再帰値を合成する。
この典型を扱う単元: XOR閾値matchingのbit分割再帰
検索別名: XOR threshold matching、XOR閾値matching
未知問からこの典型を見つける手掛かり
- 扱う対象
- XOR閾値
- pair
- 整数集合
- 最大matching数
- 使う手掛かり
- XORが閾値以上
- medianの可否
- pair可能数の最大化
- 保つ不変量
- 下位bitへ残すpair
- 最上位の異なるbit
- 確定cross pair
- 求めるもの
- matching feasibility
- 閾値を満たす最大pair数
- 適用しない条件
- XOR minimax
- 上位bitからmaskを固定するfeasibility greedy
分類・前提・学習成果
分類と直接の前提
概念上の親: モデル変換
関連する典型
- 上位bitの支配関係によるXOR minimax: XOR閾値を満たすpairの最大matching数をbit再帰で求める判定器と、共通maskを選んで全pairの最大XORを最小化する再帰を区別する。
- 単調境界探索: 固定XOR閾値での最大matching数をbit再帰で判定し、その成立数が閾値に対して単調な場合に外側の二分探索と組み合わせる。
学習成果と学習単位
整数集合を上位bitで分け、XORが固定閾値以上となる最大pair数を、同一集合内と二集合間の再帰関数へ分解して正しく合成できる。閾値bitごとのcross pairの確定条件と最大性を証明できる。
XOR閾値matchingのbit分割再帰で学ぶ
代表問題
この典型の考え方を具体的な問題で確かめるための入口です。
関連問題
この典型が主タグまたは補助タグとして付いている問題です。