hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://yukicoder.me/problems/no/733 前提知識 O(3^N)の部分集合の列挙を使ったbitDP 解法 https://yukicoder.me/submissions/283452この問題はbitDPを知っていないと解くのは難しい。 ok配列をまず作ろう。 ok[msk] := 集合mskの問題を1人でT時間以内に解けるか これはO(N2^N)で用意できる。 次に、dp配列を作る。 dp[msk] := 集合mskの問題をT時間以内に解くのに必要な最少人数 O(3^N)で部分集合を列挙することで全ての遷移を試す。 msk-msk2からmskへの遷移を考えたと… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2018%2F09%2F07%2F232917" title="分身並列コーディング [yukicoder No.733] - はまやんはまやんはまやん" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2018-09-07 23:29:17 rich https://blog.hamayanhamayan.com/entry/2018/09/07/232917 1.0 100%