概要

各依頼で指定された複数リソースに共通してアクセスできるような権限ビット列 \(K\) のうち、二進数として最小のものを求めます。

考察

リソース \(i\) に必要な権限が \(S_i\) のとき、アクセス条件は \(K \mathbin{\&} S_i = S_i\) です。これは「\(S_i\) で 1 になっているビットは、\(K\) でも必ず 1 でなければならない」という意味です。

ある依頼でリソース集合 \(\{c_1, c_2, \dots\}\) にアクセスしたいなら、\(K\) はそれらすべてを満たす必要があるため、

• \(S_{c_1}\) の 1 ビットは \(K\) で 1
• \(S_{c_2}\) の 1 ビットも \(K\) で 1
• …

となり、結局 どれか1つでも要求されるビットは \(K\) で 1 でなければいけません。これはビットごとの和集合であり、次の式で表せます： \(K \supseteq S_{c_1} \lor S_{c_2} \lor \cdots\)

さらに「二進数として最小」にするには、必要なビット以外は 0 にするのが最善です。よって最小の \(K\) は

\[K = S_{c_1} \lor S_{c_2} \lor \cdots\]

になります。

具体例

\(L=5\) として、 - \(S_1 = 00101\) - \(S_3 = 10000\)

に両方アクセスしたいなら、必要なビットを全部立てた - \(K = 00101 \lor 10000 = 10101\)

が最小です。これより小さくするにはどこかの 1 を 0 にする必要がありますが、それをすると対応するリソースにアクセスできなくなります。

素朴に「条件を満たす \(K\) を探す」ような探索は候補が \(2^L\) 個あり（最大 \(2^{64}\)）、不可能です。一方、上の観察により各クエリは OR を取るだけで済みます。

アルゴリズム

1. 各 \(S_i\)（長さ \(L\) のビット列）を整数（2進数）として読み込み、配列に保持する。
   
   • \(L \le 64\) なので Python の int で安全に扱えます。
2. 各依頼について、指定されたリソースの整数値を順に OR して val を作る：
   • val |= S[idx]
3. val を長さ \(L\) の2進文字列（先頭 0 埋め）にして出力する。

計算量

• 時間計算量: \(O\!\left(N + \sum_{j=1}^{Q} M_j\right)\)
  （各クエリは指定個数ぶん OR をするだけ）
• 空間計算量: \(O(N)\)
  （各リソースのビット列を整数で保持）

実装のポイント

• 高速入力：\(N,Q,\sum M_j\) が最大 \(10^5\) なので、sys.stdin.buffer.read().split() でまとめて読むと安定します。

• 先頭 0 埋め出力：format(val, "0{}b".format(L)) を使うと長さ \(L\) に揃えられます。

• 文字列同士でビット演算を毎回行うより、整数にして OR するほうが簡潔で高速です。

  ソースコード

import sys

def main():
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    N = int(next(it))
    L = int(next(it))
    Q = int(next(it))

    S = [0] * (N + 1)
    for i in range(1, N + 1):
        S[i] = int(next(it).decode(), 2)

    fmt = "0{}b".format(L)
    out_lines = []

    for _ in range(Q):
        m = int(next(it))
        val = 0
        for _ in range(m):
            idx = int(next(it))
            val |= S[idx]
        out_lines.append(format(val, fmt))

    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

---

この解説は gpt-5.2-high によって生成されました。