\(D\) 日目までに条件を達成できるかを考え、二分探索をします。

従業員とメダルの組を表す\(N \times K\) 頂点とそれぞれの日を表す \(D\) 頂点からなる \(N \times K + D \) 頂点の二部グラフを考えます。

従業員とメダルの組を表す\(N \times K\) 頂点からなる集合を \(U\) とします。

それぞれの日を表す頂点から、その日に出勤する従業員に対応する頂点に向けて辺を張ります。このとき、問題の条件は「\(U\) を全てカバーするマッチングが存在すること」と同値です。

結婚定理を用いると、この条件は「任意の \(U\) の部分集合 \(A\) について、 \(|A| \leq |\Gamma(A)|\) 」と言い換えられます。

\(|\Gamma(A)|\) の値は \(A\) に含まれる従業員の集合のみによって決まるため、ある従業員に対応する頂点について、\(A\) に \(1\) つも含まれていない場合と、全て含まれている場合のみを考えれば十分です。

したがって、従業員の空でない部分集合全てについて、\(D\) 日目までの間にその部分集合に含まれる人が \(1\) 人以上出勤している日数を求められればよいです。これはそれぞれの日に出勤する人の集合を求め、高速ゼータ変換を適用することで計算できます。

また、\(2 N K\) 日目以降においては \( |A| \leq NK \leq |\Gamma(A)|\) を満たすため、高々 \(2 N K\) 日で条件を達成できることが分かります。

全体の計算量は \(O((NK + N \cdot 2^N) \log(NK))\) です