概要

各リソースに必要な権限ビット列が与えられ、複数のリソースにアクセスできる最小の権限ビット列を求める問題です。

考察

問題の核心は、複数のリソースにアクセスするために必要な最小の権限ビット列を見つけることです。各リソース \(i\) には必要な権限ビット列 \(S_i\) が定義されており、社員の権限ビット列 \(K\) が \(K \mathbin{\&} S_i = S_i\) を満たすとき、そのリソースにアクセスできます。

重要な観察は、複数のリソースにアクセスするためには、各リソースが要求するすべての権限を合わせたものが必要だということです。つまり、必要な権限はすべての \(S_i\) のビットごとのORを取ったものと等しくなります。このORを取った値を \(K\) とすると、これは条件を満たす最小の値になります。なぜなら、これより小さい値では必要な権限のうち少なくとも1つが欠けてしまうからです。

アルゴリズム

1. 各リソースの権限ビット列を整数値に変換する
2. 各クエリについて、指定されたリソースの権限ビット列のビットごとのORを計算する
3. 得られた整数値を長さ \(L\) の2進数文字列に変換して出力する

具体的には、クエリで与えられたリソース集合を \(R\) とすると、求める権限ビット列 \(K\) は： $\(K = \bigvee_{i \in R} S_i\)\( となります（\)\vee$ はビットごとのOR演算）。

計算量

• 時間計算量: \(O(N \cdot L + \sum M_j)\)
  • 権限ビット列の整数変換に \(O(N \cdot L)\)
  • クエリ処理に各クエリでOR演算を行うため \(O(\sum M_j)\)
• 空間計算量: \(O(N + \sum M_j)\)
  • 権限ビット列の整数表現の保存とクエリデータの保持

実装のポイント

• ビット列を整数に変換する際は、左シフトとOR演算を組み合わせると効率的です

• 出力時にビット列の長さが \(L\) になるよう、先頭にゼロを補填する必要があります

• クエリで指定されるリソース番号は1-indexedなので、0-indexedに変換する必要があります

  ソースコード

import sys

def main():
    data = sys.stdin.read().splitlines()
    if not data:
        return
    
    first_line = data[0].split()
    N = int(first_line[0])
    L = int(first_line[1])
    Q = int(first_line[2])
    
    S_list = []
    for i in range(1, 1 + N):
        S_list.append(data[i].strip())
    
    queries = []
    index = N + 1
    for i in range(Q):
        parts = data[index].split()
        index += 1
        M_j = int(parts[0])
        resources = list(map(int, parts[1:1+M_j]))
        queries.append(resources)
    
    # Precompute the integer representation of each S_i
    S_ints = []
    for s in S_list:
        num = 0
        for char in s:
            num = (num << 1) | (1 if char == '1' else 0)
        S_ints.append(num)
    
    results = []
    for resources in queries:
        required_mask = 0
        for r in resources:
            idx = r - 1
            required_mask |= S_ints[idx]
        
        # We need to find the minimum K such that (K & required_mask) == required_mask
        # Actually, the minimal K is exactly required_mask itself.
        # Because if we set K = required_mask, then for each resource, we have exactly the required bits.
        # Any smaller value would miss at least one required bit.
        k_val = required_mask
        
        # Convert to binary string of length L
        bin_str = bin(k_val)[2:]
        if len(bin_str) < L:
            bin_str = '0' * (L - len(bin_str)) + bin_str
        results.append(bin_str)
    
    for res in results:
        print(res)

if __name__ == "__main__":
    main()

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