まず初めに問題文通りに \(i=1,2,\ldots,N\) についてそれぞれ \(i\) 日目にすぬけ君が食材 \(B_i\)​ を克服した直後、すぬけ君が食べることができるAtCoderレストランの料理の個数を求めることを考えます。ある食材が苦手か苦手でないかを配列で持ち、 \(i=1,2,\ldots ,N\) の順に求めていくとして、各 \(i\) について \(M\) 個の料理それぞれについて含まれる食材を全種類見て料理が食べられるか判定するという方法が考えられます。しかし、この方法では最悪計算量は \(\mathrm{\Theta }(N(\sum K_i +M))\) になり、問題の制約下では正解を得ることは難しいです。

この解法のどこがボトルネックかを考えてみましょう。毎日全料理見ているのがまず一番のボトルネックです。毎日全料理見るのではなく前日からの差分を考え、その日克服した食材が含まれる料理だけを見れば良いです。なぜならば、\(i\) 日目に食材 \(B_i\) を克服したとき、食べられなかった料理で食べられるようになるかもしれない料理は食材 \(B_i\) が含まれるもののみだからです。\(i\) 日目時点で食材 \(B_i\) が含まれる料理について食材 \(B_i\) を克服して食べられるようになるかは、各料理に含まれる苦手な食材の種類数を管理し更新していけば判定できます。

よって、\(1\) 日目から順に苦手な食材を見ていって、各料理に含まれる苦手な食材の種類数を更新していき、\(0\) 種類になったら食べられる料理として答えに \(1\) 加算するといった方法を用いると求めることができます。具体的にはある食材が苦手でなくなったとき、その食材を含むすべての料理について苦手な食材の種類数を \(1\) 減らす操作をすれば良いです。また、ある食材を含む料理の一覧は二次元配列などを用いて管理することができます。

ある料理に使われている食材の種類数の総和と各食材についてそれが含まれる料理の個数の総和は等しいです。また、この値は \(\sum K_i\) です。つまり、時間計算量 \(\mathrm{O}(N+\sum K_i)\) で更新していくことができます。

全体で計算量は \(\mathrm{O}(N+M+\sum K_i)\) になります。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(m);
    vector<vector<int>> idx(n);
    vector<int> cnt(m);
    for (int i = 0; i < m; ++i) {
        int k;
        cin >> k;
        cnt[i] = k;
        a[i].resize(k);
        for (auto &e : a[i]) {
            cin >> e, e--;
            idx[e].push_back(i);
        }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int b;
        cin >> b;
        b--;
        for (auto id : idx[b]) {
            cnt[id]--;
            if (cnt[id] == 0)
                ans++;
        }
        cout << ans << endl;
    }
}