概要

\(N\) 人の候補者から、選んだ全員のスキル値のビットごとのORがちょうど目標値 \(K\) に一致するように、最大何人選べるかを求める問題です。

考察

重要な気づき①：候補者のフィルタリング

ビットごとのOR演算の性質として、一度立ったビットは消えないという点があります。つまり、ある候補者 \(i\) のスキル値 \(A_i\) に \(K\) では立っていないビットが含まれている場合、その候補者をチームに入れると、チーム全体のORに余計なビットが立ってしまい、ORが \(K\) を超えてしまいます。

したがって、チームに入れられる候補者は \(A_i\) が \(K\) の部分マスク（submask）であるもの、すなわち \(A_i \mathbin{\&} K = A_i\)（あるいは同値で \(A_i \mathbin{|} K = K\)）を満たすものに限られます。

重要な気づき②：最大人数を求めるには全員入れればよい

条件を満たす候補者（部分マスクである候補者）は、どれを選んでもORに余計なビットを加えません。よって、条件を満たす候補者は全員チームに入れて問題ないのです。むしろ、人数を最大化したいのですから、全員入れるのが最善です。

ただし、全員入れた結果のORが \(K\) にちょうど等しくなるかは確認が必要です。ORが \(K\) に足りない場合（\(K\) のあるビットをカバーする候補者がいない場合）、答えは存在しません。

素朴なアプローチが不要な理由

全 \(2^N\) 通りの部分集合を列挙するのは \(N\) が最大 \(2 \times 10^5\) なので到底不可能ですが、上記の考察により貪欲に全員入れるだけで解けるため、列挙は不要です。

アルゴリズム

1. 各候補者 \(A_i\) について、\(A_i \mathbin{\&} K = A_i\) を満たすか判定し、満たすものだけを集める（valid リスト）。
2. valid が空なら、答えは \(-1\)。
3. valid に含まれる全要素のORを計算する。
4. そのORがちょうど \(K\) に等しければ、答えは valid の要素数（＝全員選ぶ）。等しくなければ \(-1\)。

具体例

\(N = 4, K = 7 \;(= 111_2)\), \(A = [3, 5, 8, 6]\) の場合：

• \(3 = 011_2\): \(3 \mathbin{\&} 7 = 3\) ✔️（部分マスク）
• \(5 = 101_2\): \(5 \mathbin{\&} 7 = 5\) ✔️
• \(8 = 1000_2\): \(8 \mathbin{\&} 7 = 0 \neq 8\) ❌（\(K\) にないビットが立っている）
• \(6 = 110_2\): \(6 \mathbin{\&} 7 = 6\) ✔️

valid = [3, 5, 6]、全体のOR \(= 3 \mathbin{|} 5 \mathbin{|} 6 = 7 = K\) ✔️

答えは \(3\) 人。

計算量

• 時間計算量: \(O(N)\)（各候補者を1回ずつ確認し、ORを計算するだけ）
• 空間計算量: \(O(N)\)（valid リストの格納）

実装のポイント

• \(K\) や \(A_i\) が最大 \(10^{18}\) と大きいですが、Python では多倍長整数を自然に扱えるため、特別な処理は不要です。

• 部分マスクの判定は (a & K) == a の一行で行えます。

• 入力が大きくなり得るので、sys.stdin.buffer.read() でまとめて読み込むと高速です。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    K = int(input_data[1])
    A = [int(input_data[i + 2]) for i in range(N)]
    
    # A candidate can be in the team only if A_i is a submask of K (i.e., A_i | K == K, equivalently A_i & K == A_i)
    # We need to select a non-empty subset of such candidates whose OR is exactly K.
    
    # Step 1: Filter candidates whose A_i is a submask of K
    valid = [a for a in A if (a & K) == a]
    
    if not valid:
        print(-1)
        return
    
    # Step 2: Check if OR of all valid candidates equals K
    total_or = 0
    for a in valid:
        total_or |= a
    
    if total_or != K:
        print(-1)
        return
    
    # Step 3: All valid candidates can be included! Because each valid candidate is a submask of K,
    # and together they OR to K. So the answer is len(valid).
    # Wait, that's correct: every valid candidate has A_i & K == A_i, so including all of them
    # gives OR = total_or = K. We want maximum number, so include all valid candidates.
    
    print(len(valid))

main()

---

この解説は claude4.6opus-thinking によって生成されました。