概要

指定された複数のリソースすべてにアクセスできる最小の権限ビット列を求める問題です。各リソースの必要権限のビットごとの OR を取ることで解けます。

考察

アクセス条件の理解

社員の権限 \(K\) でリソース \(i\) にアクセスできる条件は \(K \mathbin{\&} S_i = S_i\) です。これは「\(S_i\) で 1 になっているビットがすべて \(K\) でも 1 になっている」ことを意味します。

具体例で考えてみましょう。\(L = 4\) のとき： - リソース1の必要権限: \(S_1 = \) 1010 - リソース2の必要権限: \(S_2 = \) 0110

リソース1にアクセスするには、1ビット目と3ビット目が 1 である必要があります。リソース2にアクセスするには、2ビット目と3ビット目が 1 である必要があります。

重要な気づき：OR を取れば十分

複数のリソースすべてにアクセスするには、どのリソースでも要求されるビットをすべて 1 にする必要があります。つまり、必要な権限は少なくとも \(S_{c_1} \mathbin{|} S_{c_2} \mathbin{|} \cdots \mathbin{|} S_{c_M}\)（ビットごとの OR）です。

逆に、この OR の結果をそのまま権限 \(K\) とすれば、各 \(S_i\) について \(K \mathbin{\&} S_i = S_i\) が成り立ちます。なぜなら、OR によって各 \(S_i\) の 1 のビットはすべて \(K\) に含まれるからです。

さらに、この OR の結果は必要最低限のビットだけを 1 にしたものなので、二進数としての値が最小になります。余分なビットを 1 にすれば値は大きくなるだけで、ビットを減らすとどれかのリソースにアクセスできなくなります。

上の例では \(K = \) 1010 \(\mathbin{|}\) 0110 \(=\) 1110 が答えです。

アルゴリズム

1. 各リソースの権限ビット列 \(S_i\) を整数に変換して保持する。
2. 各クエリについて、指定されたリソースの権限ビット列をすべて OR で合成する。
3. 結果を長さ \(L\) のビット文字列に変換して出力する。

計算量

• 時間計算量: \(O(N \cdot L + \sum_{j=1}^{Q} M_j)\)
  • 前処理（ビット列の読み込みと整数変換）に \(O(N \cdot L)\)
  • 各クエリで \(M_j\) 個のリソースの OR を取るのに \(O(M_j)\)（整数の OR は \(O(1)\)）
  • \(\sum M_j \leq 10^5\) なので全体で十分高速
• 空間計算量: \(O(N)\)
  • 各リソースの権限を整数として保持

実装のポイント

• ビット列は文字列 "1010" のように与えられるので、int(s, 2) で二進数として整数に変換すると、ビット演算が簡単に行えます。

• 出力時は format(result, '0Lb') （L は桁数）で、先頭のゼロ埋めを含む長さ \(L\) のビット文字列に変換できます。

• \(L \leq 64\) なので、Python の整数演算で問題なく扱えます（C++ 等では unsigned long long で対応可能）。

  ソースコード

import sys
input = sys.stdin.readline

def main():
    N, L, Q = map(int, input().split())
    S = []
    for i in range(N):
        s = input().strip()
        # Convert bit string to integer
        val = int(s, 2)
        S.append(val)
    
    for _ in range(Q):
        line = list(map(int, input().split()))
        M = line[0]
        resources = line[1:M+1]
        # OR all required permission bit strings
        result = 0
        for c in resources:
            result |= S[c - 1]
        # Convert back to bit string of length L
        print(format(result, '0' + str(L) + 'b'))

main()

---

この解説は claude4.6opus-thinking によって生成されました。