概要

複数のリソースにアクセスするために必要な「最小の権限」を求める問題です。各リソースの必要権限はビット列で表されており、それらすべてを包含する最小のビット列を計算します。

考察

1. アクセス条件の理解

ある社員の権限 \(K\) がリソース \(i\) の必要権限 \(S_i\) を満たす条件は \(K \mathbin{\&} S_i = S_i\) です。 これはビット単位で見ると、「\(S_i\) で 1 になっているビットは、\(K\) でも必ず 1 になっていなければならない」 ということを意味します。逆に、\(S_i\) が 0 であるビットについては、\(K\) は 0 でも 1 でも条件を満たします。

2. 複数のリソースを同時に満たすには

1つの依頼で複数のリソース \(\{c_1, c_2, \dots, c_M\}\) が指定された場合、それらすべてに対して条件を満たす必要があります。 つまり、「指定されたいずれかのリソースにおいて、あるビットが 1 であれば、社員の権限 \(K\) でもそのビットは 1 でなければならない」 ということになります。

3. 最小の値を求める

「ビット列を二進数として解釈したときの値を最小にする」ためには、必要不可欠なビット以外はすべて 0 にすればよいです。 したがって、求める最小の権限 \(K\) は、指定されたすべてのリソースの必要権限 \(S_i\) について、ビットごとの論理和（OR） を取ったものになります。

具体例

• リソース1: 1010
• リソース2: 1100 これら両方にアクセスしたい場合、
• 1番目のビット：両方 1 なので \(K\) も 1
• 2番目のビット：リソース2が 1 なので \(K\) も 1
• 3番目のビット：リソース1が 1 なので \(K\) も 1
• 4番目のビット：両方 0 なので \(K\) は 0 でよい（最小化のため） 結果：1110 （これは 1010 | 1100 の結果と一致します）

アルゴリズム

1. 各リソースの必要権限 \(S_i\)（文字列）を、計算しやすいように整数型に変換して配列に格納します。
2. 各クエリ（依頼）に対して、以下の処理を行います。
   • 変数 res_val を \(0\) で初期化します。
   • 依頼に含まれる各リソース番号 \(c_{j,k}\) について、res_val |= S[c_{j,k}] （ビットごとの論理和）を計算します。
   • 最終的な res_val を、長さ \(L\) の 2進数文字列に変換して出力します。

計算量

• 時間計算量: \(O(N + \sum M_j + QL)\)
  • リソースの読み込みと整数変換に \(O(N)\)。
  • 全クエリを通じたリソースの参照と OR 演算の回数は \(\sum M_j\) であり、制約より \(10^5\) 以下です。
  • 出力文字列の生成に \(O(QL)\) かかります。
• 空間計算量: \(O(N)\)
  • リソースの必要権限を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) や \(Q\)、\(\sum M_j\) が \(10^5\) と大きいため、Pythonでは sys.stdin.read().split() を使って入力を一括で読み込んだり、結果をリストに貯めて最後に join して出力したりすることで実行時間を短縮できます。

• 2進数文字列のフォーマット: 整数を \(L\) 桁の 2進数文字列（0 埋め）に変換するには、format(val, '0' + str(L) + 'b') や f-string を使うと便利です。

  ソースコード

import sys

def solve():
    """
    権限管理システムの最小権限ビット列を求める問題を解く関数です。
    
    各リソース Si にアクセスするための最小の権限 K は、
    K & Si = Si を満たす必要があります。
    複数のリソースに対してこの条件を満たす最小の K は、
    それらのリソースの必要権限 Si のビットごとの論理和 (OR) です。
    """
    
    # 全ての入力を一度に読み込み、空白で分割してイテレータを作成します。
    # これにより、大量の入力を高速に処理できます。
    try:
        input_data = sys.stdin.read().split()
    except EOFError:
        return
        
    if not input_data:
        return
    
    it = iter(input_data)
    
    # N: リソースの数, L: ビット列の長さ, Q: 依頼の数
    try:
        N = int(next(it))
        L = int(next(it))
        Q = int(next(it))
    except StopIteration:
        return
    
    # 各リソースの必要権限 Si を整数のリストとして格納します。
    # 2進数文字列を整数に変換して保持することで、ビット演算を高速化します。
    S = [0] * N
    for i in range(N):
        try:
            S[i] = int(next(it), 2)
        except StopIteration:
            break
            
    # 出力形式（長さ L の 0 埋め 2 進数文字列）を指定するためのフォーマット文字列を作成します。
    fmt_str = '0' + str(L) + 'b'
    results = []
    
    # 各依頼（クエリ）を順番に処理します。
    for _ in range(Q):
        try:
            # M_j: 依頼に含まれるリソースの数
            M_j = int(next(it))
            res_val = 0
            # 指定されたすべてのリソースの必要権限のビット論理和を計算します。
            for _ in range(M_j):
                # リソース番号は 1-indexed なので、0-indexed に変換します。
                idx = int(next(it)) - 1
                res_val |= S[idx]
            
            # 計算された最小の権限ビット列を、指定されたフォーマットで文字列に変換します。
            results.append(format(res_val, fmt_str))
        except StopIteration:
            break
            
    # 全ての依頼に対する結果を改行区切りで結合し、一度に出力します。
    if results:
        sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

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