\(G_i:=(\) 動物園 \(i\) にいる動物 \()\) と定義します。

ここで、同じ動物園に \(3\) 度以上行く必要はないため、各動物園への訪問回数を最大 \(2\) 回とみなして bit 全探索 を行います。

具体的には、\(S=0,1,2,\dots,2^{2N}-1\) について for ループを回し、\(S\) の \(2^k\) の位が \(1\) ならば動物園 \(\lfloor k/2\rfloor+1\) に \(1\) 回訪れたとすることで全探索が可能です。各訪問で見られる動物 \(j\) の回数を \(G_i\) を用いて計算することで十分高速に処理することができます。

計算量は \(O(4^NNM)\) です。公式解説のアルゴリズムより大きいですが、実装が容易であり、制約内では十分高速に動作します。

実装例 ( PyPy3 , 1672 ms )

実装例 ( C++ , 618 ms )