クエリを受け取るごとに次の力任せ探索を行えばこの問題を解くことができます。

• はじめ、\(\text{answer} = -1, \text{score} = -1\) とする。
• \(i=1, 2, \dots, N\) について、次の処理を行う。
  • 薬 \(i\) がその人に与えて良い薬かを判定する。
    • 判定については、その人の持つすべてのアレルゲン \(Y_j\) が \(\lbrace X_{i,1},\dots,X_{i,C_i}\rbrace\) に含まれなければ与えて良い薬、そうでなければ与えてはいけない薬であると判定できる。
  • もし薬 \(i\) が与えて良い薬で、かつ \(A_i \gt \text{score}\) ならば、\(\text{answer} \gets i, \text{score} \gets A_i\) に更新する。
• 処理を行った後の \(\text{answer}\) がクエリの答えである。

アルゴリズムの計算量は \(\mathrm{O}(N \sum_{i=1}^Q D_i)\) 程度で、この問題を 正答できる程度に十分高速です。

• 実装例(C++)

#include <iostream>
#include <vector>
using namespace std;

bool C[110][200010];
int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  vector<int> A(N);
  for (auto& a : A) cin >> a;
  for (int i = 0, s, x; i < N; i++) {
    cin >> s;
    while (s--) cin >> x, C[i][x] = true;
  }
  int Q;
  cin >> Q;
  while (Q--) {
    int d;
    cin >> d;
    vector<int> v(d);
    for (auto& x : v) cin >> x;
    int answer = -1, score = -1;
    for (int i = 0; i < N; i++) {
      int ok = true;
      for (auto& x : v) ok &= ~C[i][x];
      if (ok and score < A[i]) answer = i + 1, score = A[i];
    }
    cout << answer << "\n";
  }
}