概要

各候補者のスキル集合（ビット）を OR で合成してちょうど \(K\) にしたいとき、選べる人数の最大値を求めます。結論として「\(K\) に含まれないビットを持つ人は絶対に選べない」ことを利用して、条件を満たす人を全員選べるかどうかを判定します。

考察

重要な気づき

部分集合の OR がちょうど \(K\) になるためには、選ぶ全員が \(K\) に存在しないビットを持っていない 必要があります。

• ある候補者の値を \(x\) とします。
• もし \(x\) に「\(K\) のそのビットが 0 なのに \(x\) では 1」というビットが1つでもあると、OR を取った瞬間にそのビットが 1 になってしまい、結果は \(K\) を超えて（異なって）しまいます。
• これは式で書くと「\((x \mid K) = K\) であること」が必要条件です。
  （\(x\) の 1 ビットがすべて \(K\) の 1 ビットに含まれている、という意味）

したがって、選べるのは [ (x \mid K) = K ] を満たす候補者だけです。

最大人数にするには？

「条件を満たす候補者」を全員入れても OR の結果は \(K\) を超えません（余計なビットが立たないため）。
また、人数を最大化したいので、可能ならその全員を入れるのが最適です。

あとは、その「条件を満たす候補者たち」を全員 OR した結果が本当に \(K\) になるかを確認すればよいです。

• 条件を満たす候補者が 0 人 → 空集合しか作れず、問題文は「空でない部分集合」なので不可能
• 条件を満たす候補者全員の OR が \(K\) にならない → どんな部分集合でも \(K\) の立つべきビットを埋められず不可能
• OR が \(K\) になる → 全員選ぶのが最大人数

具体例

\(K=10(=1010_2)\)、候補者が \([2(0010), 8(1000), 1(0001)]\) のとき： - \(2|10=10\) → 選べる - \(8|10=10\) → 選べる - \(1|10=11\neq 10\) → 選べない（\(K\) にない下位ビットを持つ） 選べる人は 2 人で、OR は \(2|8=10\) なので答えは 2。

アルゴリズム

1. 各 \(A_i\) について、\((A_i \mid K) = K\) を満たすものだけを「選択可能」として数える（cnt）。
2. 選択可能なものをすべて OR した値を orv とする。
3. cnt==0 または orv != K なら -1 を出力。
4. そうでなければ、最大人数は選択可能な全員なので cnt を出力。

計算量

• 時間計算量: \(O(N)\)（各要素を1回見るだけ）
• 空間計算量: \(O(1)\)（入力配列以外は定数個の変数）

実装のポイント

• 判定条件は「\(A_i\) が \(K\) の部分集合のビットである」ことなので、(Ai | K) == K を使うと簡潔です。

• 「最大人数」を求める問題ですが、今回は「選べるなら全員選ぶのが最適」という単調性があるため、DP や全探索は不要です。

• 空でない部分集合が条件なので、選択可能人数 cnt が 0 の場合は必ず -1 になります。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, K = data[0], data[1]
    A = data[2:2+N]

    cnt = 0
    orv = 0
    for x in A:
        if (x | K) == K:
            cnt += 1
            orv |= x

    if cnt == 0 or orv != K:
        print(-1)
    else:
        print(cnt)

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。