概要

\(N\) 人の候補者から、スキルのビットごとの論理和（OR）がちょうど \(K\) となるようにメンバーを選んだときの、最大人数を求める問題です。

考察

この問題の鍵は、「どの候補者がチームに入る可能性があるか」を絞り込むことにあります。

1. 候補者の選別

チーム全体のスキルの OR をちょうど \(K\) にしたい場合、チームに加わる各メンバーのスキル \(A_i\) は、以下の条件を満たしている必要があります。 - \(A_i\) で立っているビットは、すべて \(K\) でも立っていなければならない。

もし \(A_i\) に、\(K\) では 0 なのに \(A_i\) では 1 であるようなビットが一つでも含まれていれば、その人を加えた時点でチーム全体の OR のそのビットは 1 になってしまい、決して \(K\) と一致させることはできなくなります。

この条件は、ビット演算を用いると (A_i | K) == K と簡潔に判定できます。

2. 最大人数の考え方（貪欲法）

「OR をちょうど \(K\) にしつつ、人数を最大化したい」という目的があります。 上記の条件を満たすすべての候補者をチームに入れたとしても、OR の結果が \(K\) を超えることはありません（\(K\) に含まれないビットが 1 になることはないため）。

したがって、「条件を満たす候補者を全員選ぶ」のが最善の戦略となります。

3. 最終的な判定

条件を満たす人を全員選んだ後、以下の 2 点を確認する必要があります。 - チームが空ではないか: 問題文に「空でない部分集合」とあるため、1人以上選ばれている必要があります。 - OR がちょうど \(K\) になっているか: 条件を満たす人を全員集めても、特定のビットを誰も持っていなければ、最終的な OR が \(K\) に届かない（\(K\) 未満になる）可能性があります。

これらを満たせば選んだ人数が答えとなり、満たさなければ条件に合うチームは作れないため \(-1\) となります。

アルゴリズム

1. 選べる人数をカウントする変数 count と、選んだメンバーの OR を保持する変数 current_or を 0 で初期化します。
2. 各候補者のスキル \(A_i\) について、以下を繰り返します。
   • もし (A_i | K) == K ならば：
     • count を 1 増やす。
     • current_or に \(A_i\) を OR 演算で加える (current_or |= A_i)。
3. ループ終了後、count > 0 かつ current_or == K であれば count を出力します。
4. そうでなければ -1 を出力します。

計算量

• 時間計算量: \(O(N)\)
  • \(N\) 人の候補者を 1 回ずつ走査するため、候補者の人数に対して線形時間で処理が終わります。
• 空間計算量: \(O(N)\)
  • 入力値をすべて保持する場合 \(O(N)\) ですが、1つずつ読み込んで処理すれば \(O(1)\) に抑えることも可能です。

実装のポイント

• ビット演算の判定: (a_i | k) == k は、「\(a_i\) が \(k\) のサブセット（ビットの部分集合）である」ことを判定する定石的な書き方です。

• 大きな整数の扱い: \(K\) や \(A_i\) は最大 \(10^{18}\) と非常に大きいため、言語によっては 64 ビット整数型（Python では自動で扱われます）を使用する必要があります。

• 空集合の除外: 誰も条件を満たさない場合に current_or が 0 になりますが、もし \(K=0\) だった場合に「誰も選んでいないのに OR が \(K\) と一致する」と誤判定しないよう、count > 0 のチェックが重要です。

  ソースコード

import sys

def solve():
    # 標準入力からすべてのデータを読み込み、スペースで分割します
    # N, K, A_1, A_2, ..., A_N の順で取得します
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    # 候補者の人数 N と目標のスキルセット K を取得
    n = int(input_data[0])
    k = int(input_data[1])
    
    # 選べる候補者の数と、選んだメンバーのスキルのビット論理和（OR）を初期化
    count = 0
    current_or = 0
    
    # 各候補者のスキル A_i についてループ
    for i in range(n):
        a_i = int(input_data[2 + i])
        
        # A_i が目標値 K のサブセット（ビットの部分集合）であるか判定
        # すなわち、A_i に含まれるすべてのビットが K にも含まれているかを確認
        # (a_i | k) == k は a_i のビットが k に包含されていることを意味します
        if (a_i | k) == k:
            count += 1
            current_or |= a_i
            
    # 条件を満たす「空でない」部分集合が存在するか判定
    # 1. count > 0: 少なくとも一人の候補者が K のサブセットである
    # 2. current_or == k: 選んだ全員のスキルの OR がちょうど K に一致する
    # このとき、選べる最大の人数は count となります
    if count > 0 and current_or == k:
        print(count)
    else:
        # 条件を満たす部分集合が存在しない場合
        print(-1)

if __name__ == '__main__':
    solve()

---

この解説は gemini-3-flash-thinking によって生成されました。