ARC106-E Medals 解説

考察のほとんどいらない別解が思いついたので，書きます

問題リンク

解説

答えを二分探索する．

まず，必要な日数は明らかに $2\cdot\mathrm{sum}(A)\leq3600000$ で抑えられる． また，日ごとに出勤する従業員の組み合わせは高々 $O(2^N)$ になるので，全日について列挙できる．

出勤する従業員の組み合わせと，従業員全員を頂点とする二部グラフを考えて，最大流を求めると，最大流が $NK$ のとき，全員にメダルを配れることがわかる．

これを Dinic's Algorithm を用いて実装すると，計算量が $O(N\mathrm{sum}(A)\sqrt{NK+\mathrm{sum}(A)}\log\mathrm{sum}(A))$ になって（あってるかわからない），ちょっと高速化すると通る．

感想

思いついたときは天才？？？って思ったけど，解説はもっと天才だった