概要

各クエリについて、指定された複数のリソースすべてにアクセスできる最小の権限ビット列を求めます。

考察

各リソースには必要な権限がビット列で与えられており、ある社員がそのリソースにアクセスできるのは、社員の持つ権限ビット列 \(K\) がそのリソースの必要ビット列 \(S_i\) を「含む」状態、つまり \(K \mathbin{\&} S_i = S_i\) となっていることです。

複数のリソースすべてにアクセスできるためには、それぞれのリソースが必要とするすべての権限を持っていなくてはいけません。言い換えれば、必要な権限全体の和集合を持つ必要があります。

これはビット演算ではOR演算に対応します。つまり、各リソースの必要権限ビット列のORを取れば、その社員が持つべき最小の権限を得ることができます。

例えば、リソース1が 1100、リソース2が 1010 なら、両方にアクセスするためには 1100 | 1010 = 1110 が必要になります。

このようにして求めたビット列が、二進数として見たときに最小になるのは自明であり（より少ないビットで済ませられない）、これが答えとなります。

素朴に各クエリで全ビットを確認しながら権限を集計しようとすると非効率ですが、ビット演算を使えば高速に処理できます。

アルゴリズム

1. 各リソースの必要権限ビット列 \(S_i\) を事前に整数（ビット列）に変換して保存しておきます。
2. クエリごとに：
   • アクセスしたいリソースに対応する \(S_i\) をすべて取り出し、
   • それらのビット列同士のORをとり、必要な最小権限を得る。
3. 得られた整数を再度ビット列（文字列）に戻して出力する。

計算量

• 時間計算量: \(O(NL + Q(M + L))\)
  • \(N\) 個のビット列を前処理で整数に変換：\(O(NL)\)
  • 各クエリで最大 \(M\) 個のビット列のORを取る処理：\(O(M)\)
  • 結果をビット列に戻す処理：\(O(L)\)
• 空間計算量: \(O(N + L)\)
  • 必要なビット列を整数で保持する配列と、出力用の一時的なビットリスト

実装のポイント

• ビット列は左端が最上位ビット（MSB）なので、ビット位置に注意してシフトする。
• リソース番号は1-indexedで入力されるので、内部では0-indexedに変換する必要がある。
• 入力を高速に読み込むために sys.stdin.read を使用している。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    N = int(data[idx]); idx += 1
    L = int(data[idx]); idx += 1
    Q = int(data[idx]); idx += 1
    
    # リソースの必要権限を整数に変換
    S = []
    for _ in range(N):
        s = data[idx]; idx += 1
        num = 0
        for i in range(L):
            if s[i] == '1':
                num |= (1 << (L - 1 - i))
        S.append(num)
    
    results = []
    for _ in range(Q):
        M = int(data[idx]); idx += 1
        resources = list(map(int, data[idx:idx+M])); idx += M
        # リソース番号を0-indexedに変換
        required = [S[r - 1] for r in resources]
        # すべての必要な権限のORを取る
        permission = 0
        for req in required:
            permission |= req
        # permissionをビット列に戻す
        bits = []
        for i in range(L):
            if permission & (1 << (L - 1 - i)):
                bits.append('1')
            else:
                bits.append('0')
        results.append(''.join(bits))
    
    print('\n'.join(results))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。