概要

候補者のスキル集合のビットORがちょうど目標値 \(K\) と一致するような部分集合のうち、最大の人数を求める問題です。

考察

1. 基本条件: 選んだメンバーのスキル値のビットORが \(K\) と完全に一致する必要があります。つまり:

   • \(K\) のすべてのビットが少なくとも1人のメンバーでカバーされている必要があります
   • \(K\) に含まれないビットが立っているメンバーは使用できません（OR結果が \(K\) を超えてしまうため）

2. \(K=0\) の特殊ケース: すべてのメンバーのスキル値が0でなければなりません。1人でも0以外の値があるとORが0になりません。

3. 有効な候補者の選別: \(K\) に含まれないビットが立っている候補者は除外します（\((a_i | K) == K\) でチェック）。

4. 必要条件の確認: \(K\) の各ビットについて、少なくとも1人の有効な候補者がそのビットを持っている必要があります。

5. 最大人数の可能性: すべての有効な候補者を使用したときのORが \(K\) と一致するなら、それら全員を選ぶことが最大人数になります。

アルゴリズム

1. \(K=0\) の場合の処理:

   • すべてのスキル値が0の候補者のみを数え、存在すればその人数を出力

2. 有効な候補者の選別:

   • 各 \(A_i\) について \((A_i | K) == K\) を満たすものだけを抽出

3. 必要条件のチェック:

   • \(K\) の各ビットについて、有効な候補者の中にそのビットを持つ人が少なくとも1人いるか確認

4. 最大人数の決定:

   • すべての有効な候補者のORを計算し、\(K\) と一致することを確認
   • 一致すれば有効な候補者の全人数を出力、一致しなければ-1を出力

計算量

• 時間計算量: \(O(N \log K)\)
  • 有効な候補者の選別: \(O(N)\)
  • ビットカウント: 各候補者に対して最大 \(\log_2 K\) ビットをチェック
• 空間計算量: \(O(N)\)
  • 有効な候補者を格納するためのリスト

実装のポイント

1. \(K=0\) のケースを最初に処理する

2. ビット演算を用いて効率的に条件チェックを行う

3. \(K\) のビット長を動的に求めて、各ビットのカバレッジを確認する

4. すべての有効な候補者のORが \(K\) と完全に一致するか最終確認する

   ソースコード

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:2+n]))
    
    if K == 0:
        # すべてのメンバーのスキルが0でなければならない
        count = 0
        for a in A:
            if a == 0:
                count += 1
        if count > 0:
            print(count)
        else:
            print(-1)
        return
    
    # Kの各ビットが立っている必要がある
    # ただし、Kにないビットが立っている候補者は除外
    valid_A = []
    for a in A:
        if (a | K) == K:
            valid_A.append(a)
        # そうでない候補者は使えない（Kにないビットを立ててしまう）
    
    if not valid_A:
        print(-1)
        return
    
    # Kのビットごとに考える
    bits = []
    k_tmp = K
    while k_tmp:
        bits.append(k_tmp & 1)
        k_tmp //= 2
    # ビット長を揃えるため、必要なら0パディング
    max_bits = len(bits)
    
    # 各ビットについて、そのビットが立っている候補者の数を数える
    count_per_bit = [0] * max_bits
    for a in valid_A:
        for i in range(max_bits):
            if (a >> i) & 1:
                count_per_bit[i] += 1
    
    # 各ビットについて、少なくとも1人はそのビットを持っている必要がある
    for i in range(max_bits):
        if (K >> i) & 1 and count_per_bit[i] == 0:
            print(-1)
            return
    
    # 最小人数は各ビットで1人ずつだが、最大人数を求めたい
    # 貪欲に、すべての候補者を使えるか試す
    # ただし、Kのビット以外は0でなければならないので、候補者はすべてKの部分集合
    # 問題は、各ビットについて少なくとも1人はいること
    # 最大人数は、基本的にはすべての候補者を使えるか？
    # ただし、すべての候補者を使ったときのORがKになるか？
    total_or = 0
    for a in valid_A:
        total_or |= a
    if total_or != K:
        print(-1)
        return
    
    # すべての候補者を使えばORはKになる
    # しかし、実際にはすべての候補者を使えるか？
    # 実は、すべての候補者を使うと、KのビットがすべてカバーされるのでOK
    # ただし、冗長な候補者（なくてもORがKになる）がいても問題ない
    # したがって、最大人数はvalid_Aの全要素数
    print(len(valid_A))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。