典型タグ

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分割再帰で学ぶ

代表問題

この典型の考え方を具体的な問題で確かめるための入口です。

関連問題

この典型が主タグまたは補助タグとして付いている問題です。