概要

\(N\) 人の候補者からなる部分集合で、各人のスキル値のビットORがちょうど \(K\) になるように選び、最大の人数を選ぶ問題。

考察

この問題の核心は「ビットOR演算の性質」を利用することです。
ビットOR演算では一度1になったビットは以降ずっと1のままなので、「最終的にORが \(K\) になる」という条件は以下のように言い換えられます：

1. 誰かが持っているビットが \(K\) のビットより多い（つまりOR > K）になってはいけない
   　→ \(K\) のビットが0になっている位置に1を持つ候補者は除外する必要があります。

2. \(K\) のビットが1になっている位置については、誰か1人以上がそのビットを持っていなければならない

したがって、以下の手順で考えます：

手順1：無効な候補者の除外

\(K\) のビットが0である位置に1を持つ候補者は、使ってしまうとORが \(K\) を超えてしまうため、除外します。

手順2：必要なビットの網羅

\(K\) のビットが1になっている各位置について、それをカバーする候補者が1人以上存在しなければなりません。
もし1人もいなければ答えは \(-1\) です。

手順3：最大人数の選出

上記条件を満たす候補者の中から、できる限り多くの人を選ぶ必要があります。
ただし、全員選んでもORが \(K\) を超えないようにする必要があります。

実は、条件1を満たす候補者を全て選んでもORは \(K\) を超えません（なぜなら禁止ビットは誰も持ってないので）。
そのため、問題は「必要なビットをカバーする最小限の人数を選び、残りはすべて選ぶ」になります。

このときのポイントは「各必須ビットをカバーする最少人数」を貪欲に選ぶことです。
具体的には、各ビットに対し、それをカバーする候補者が複数いる場合、被らせる必要はありません。

しかし実際には、各ビットに最低1人割り当てるという形で十分であり、それ以外の人はすべて選んでもOKです。

したがって、以下の流れで解けます： 1. 条件1に該当しない候補者を抽出 2. 各必須ビットを誰かが持っているか確認 3. 全員使えるので、候補者数をそのまま出力

最初の誤解として、「最小カバーセット」を厳密に求めようとしたコードが混在していましたが、今回のケースでは全員選んでもOKなので、不要です。

アルゴリズム

1. 入力を読み込みます。
2. \(K\) のビットが0である位置に1を持つ候補者を除外します。
3. 残った候補者のうち、\(K\) の各ビット（1であるもの）を誰かがカバーしているか確認します。
4. すべてのビットがカバーされていれば、残った候補者全員を選べるので人数を出力します。
5. そうでなければ \(-1\) を出力します。

計算量

• 時間計算量: \(O(N \log K)\) （ビット操作と候補者フィルタリング）
• 空間計算量: \(O(N)\)

実装のポイント

• \(K\) のビットが0の位置に1を持つ候補者は絶対に選んではいけない
• 各required bit（\(K\) の1になっているビット）を誰かが持っているか確認する
• 最終的には候補者全員を使えるので、人数をそのまま出力すれば良い

## ソースコード

```python
def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    K = int(data[1])
    A = list(map(int, data[2:]))

    # スキル値のビット位置を管理する
    # Kのビットが立っている位置について、少なくとも1人はそのビットを持っていなければならない
    # Kのビットが立っていない位置については、誰もそのビットを持っていてはいけない

    # まず、Kのビットが立っていない位置に1を持つ候補者は除外する
    # なぜなら、それがあると OR が K を超えてしまうため
    max_bit = 60  # 10^18 < 2^60
    mask = (1 << max_bit) - 1  # 全ビットが1のマスク
    forbidden_mask = (~K) & mask  # Kで0になっているビットの位置

    valid_candidates = []
    for a in A:
        if a & forbidden_mask:
            continue
        valid_candidates.append(a)

    if not valid_candidates:
        print(-1)
        return

    # 次に、Kのビットが立っている位置について、それぞれをカバーする候補者がいるか確認
    required_bits = []
    for i in range(max_bit):
        if K & (1 << i):
            required_bits.append(i)

    # 各required bitをカバーする候補者のリスト
    covered_by = [[] for _ in range(len(required_bits))]
    for idx, a in enumerate(valid_candidates):
        for i, bit_pos in enumerate(required_bits):
            if a & (1 << bit_pos):
                covered_by[i].append(idx)

    # それぞれのビットをカバーする候補者がいなければ-1
    for cover_list in covered_by:
        if not cover_list:
            print(-1)
            return

    # 貪欲法: 最大人数を選ぶために、できるだけ多くの人を選んで、最終的にORがKになるか確認
    # すべてのrequired bitsがカバーされている範囲で、最大の部分集合を選ぶ
    # これは貪欲に、各required bitに対して1人だけ割り当て、残りは自由に追加できると考える

    # 実際には、ORがKになる最大の部分集合を効率的に見つける必要がある
    # 方法: 必要最小限の候補者を選んで各required bitをカバーし、その後、他の候補者を追加してもORがKを超えないようにする

    # 必須の候補者を決める: 各required bitについて1人ずつ担当させる（被り可）
    # この担当者たちを含む最大集合を構築する

    assigned = [False] * len(valid_candidates)
    mandatory = []

    for i in range(len(required_bits)):
        found = False
        for idx in covered_by[i]:
            if not assigned[idx]:
                assigned[idx] = True
                mandatory.append(idx)
                found = True
                break
        if not found:
            # すでに誰かが担当している場合でもOK（被りあり）
            # 最低1人は必要なので、被ってもよい
            # ただし、全員が既にassignedなら新しい人がいない
            # ここでは、各bitに1人以上割り当てられていればOK
            pass

    # 実際には、各bitをカバーする人がいれば良いので、貪欲に各bitに1人割り当て
    # 被らないようにするのが最適とは限らないので、別の方法を考える

    # 効率的な方法:
    # 1. valid_candidatesの中で、Kの禁止ビットを持たないもののみを使う
    # 2. その中で、ORをK以下に保ちながら最大の部分集合を選ぶ
    # 3. さらに、ORがちょうどKになるようにする

    # これは部分集合のORがKになるものを選ぶ問題
    # 半分全列挙はN=2*10^5では無理

    # 別のアイデア：
    # 候補者をフィルタリングした後、ORがKを超えない最大部分集合を取り、それがKに一致するか見る
    # しかし、最大部分集合のORがK未満でも、他の候補者を追加することでKにできるかもしれない

    # 高速化のため、Kのビットが立っている箇所に注目
    # 各候補者のうち、Kで0のビットに1を持たないもののみ有効

    # Kで0のビットに1を持つ候補者は除外
    # 残った候補者のORがKと一致する最大部分集合を探す

    # 最大独立集合のような問題だが、今回はORがKと一致する最大部分集合

    # 重要な観察：ORがKと一致する ⇔ 
    # 1. すべての候補者のOR <= K （Kで0のビットに1がない）
    # 2. すべてのKで1のビットについて、少なくとも1人が持っている

    # ステップ:
    # 1. 無効な候補者を除外（Kで0のビットに1を持つ）
    # 2. 残った候補者のうち、Kの各ビットをカバーする人がいるかチェック
    # 3. カバーされているなら、最大人数を選ぶ

    # 最大人数の選び方：
    # 各required bitについて最低1人は必要 → 最低人数はその数
    # 残りは好きに選んでよい（ただしORがKを超えないように）

    # 実装:
    # まず、各候補者がKの禁止ビットを持つか判定
    # 次に、Kの各ビットが誰かにカバーされているか判定
    # 最後に、最大の部分集合を構築

    # 判定後、最大人数を求める
    # 貪欲に、各ビットをカバーする最小人数を選び、残りは全部選ぶ

    # 各required bitをカバーする最小の候補者を選ぶ
    # これはset cover problemでNP-hardだが、貪欲近似で良い
    # ただし、今回は各ビットをカバーする人がいれば良いので、各ビットに1人割り当てればOK

    # つまり、各required bitに対して1人ずつ選び、残りは全部選んでもOK

    # 実装:
    # covered_by[i]: required_bits[i]をカバーする候補者のindexリスト
    # 各ビットをカバーする人がいればOK
    # 各ビットから1人ずつ選ぶ（できるだけ重複を避けて）
    # 残りは全部選んでもORはKを超えない

    # 最小カバーを求める: 各ビットから1人ずつ選ぶ
    # これは最小ヒープなどで貪欲に選んでも良いが、今回は単純に各ビットから1人選ぶだけで良い
    # 重複を許すと人数が減るので、重複を避けるのが良い

    # ただし、ビット数は最大60程度なので、各ビットから1人ずつ選ぶのは現実的

    # 実装:
    from collections import defaultdict
    import heapq

    # 各候補者がカバーするrequired bitsのリスト
    candidate_covers = []
    for i, a in enumerate(valid_candidates):
        covers = []
        for j, bit_pos in enumerate(required_bits):
            if a & (1 << bit_pos):
                covers.append(j)
        candidate_covers.append((len(covers), i, covers))  # (被覆数, index, 被覆リスト)

    # 被覆数が多い順にソートして、貪欲に選ぶ
    candidate_covers.sort(reverse=True)

    # 各ビットがカバーされているか
    covered = [False] * len(required_bits)
    selected_indices = set()

    # 各ビットをカバーするために候補者を選択
    for _, idx, covers in candidate_covers:
        added = False
        for bit_idx in covers:
            if not covered[bit_idx]:
                added = True
        if added:
            selected_indices.add(idx)
            for bit_idx in covers:
                covered[bit_idx] = True

    # すべてのビットがカバーされたか確認
    if not all(covered):
        print(-1)
        return

    # 残りの候補者はすべて選んでもOK（ORがKを超えない）
    total_selected = len(valid_candidates)
    print(total_selected)

if __name__ == "__main__":
    main()

---

この解説は qwen3-coder-480b によって生成されました。