ユーザ解説 の解法を更に高速化します．

DFS中の各時点において，動物 \(i\) を見た回数 \(F_i\) の代わりに，\(G_i \coloneqq \min(F_i, 2)\) を管理することを考えます．これは \(2\) bit あれば表現することができるので，合計 \(2M\) bit の多倍長整数 watched として持つことができます．

DFSを行う上では watched に対して以下の操作ができれば良いです．

1. ある動物園に存在する全ての動物 \(i\) に対し，\(G_i\) を \(\min(G_i + 1, 2)\) に更新する
2. 全ての動物を \(2\) 度以上見たか判定する

詳細は後述しますが，次の実装例ではこれらの操作を共に（ワードサイズを \(W\) として）\(O(M/W)\) 時間で達成します．

従って全体で \(O(3^N M/W)\) 時間で解けます．

n, m = map(int, input().split())
cost = tuple(map(int, input().split()))
zoo = [[] for _ in range(n)]
for animal in range(m):
    _, *a = map(lambda s_: int(s_) - 1, input().split())
    for j in a:
        zoo[j].append(animal)

ones = [sum(1 << 2 * j for j in z) for z in zoo]
two_all = sum(2 << 2 * j for j in range(m))

def add_one(watched, one):
    """
    `one`に存在する動物に対応する"位"だけを以下のように変化させ，そうでない"位"はそのままにする
    - `00` => `01`
    - `01` => `10`
    - `10` => `10`
    """
    return watched + (one & ~watched >> 1)

def dfs(i, watched, ans):
    if i == n:
        return ans if watched == two_all else 10**18
    ans0 = dfs(i + 1, watched, ans)
    watched = add_one(watched, ones[i])
    ans1 = dfs(i + 1, watched, ans + cost[i])
    watched = add_one(watched, ones[i])
    ans2 = dfs(i + 1, watched, ans + cost[i] * 2)
    return min(ans0, ans1, ans2)

print(dfs(0, 0, 0))

操作1が \(O(M/W)\) でできること

当該動物園で動物 \(i\) が見られるなら \(E_i \coloneqq 1\)，見られないなら \(E_i \coloneqq 0\) で \(E_i\) を定めると，操作1は

• 全ての動物 \(i\) に対し，\(G_i\) を \(\min(G_i + E_i, 2)\) に更新する

と言い換えられます．

one \( = E_i \in \lbrace 0, 1\rbrace\), w \( = G_i \in \lbrace 0, 1, 2\rbrace \) の各組み合わせについて調べると次表のようになり，いずれも w + (one & ~w >> 1)と \(\min(G_i + E_i, 2)\) が一致することが分かります．

よって上の実装例で操作1に対応する関数 add_one の正当性が確認できました．

操作2が \(O(M/W)\) でできること

全ての動物 \(i\) に対し ，

\[ F_i \ge 2 \iff G_i (= \min(F_i, 2) ) = 2 \]

であるので，watched の全ての “位” が 10 になっているか判定すれば良く，これはある定数（実装例におけるtwo_all）との等値比較でできます（実装例 23 行目）．