想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。 実際、Benqは本番これで通しているらしい これを証明する。 問題文中で定義されている目的関数をfとする。これがM凸であることを示す。 …

自分用メモなので簡略に書く 最近気づいたけどlatex記法より手書き+写真のほうが早いぜ d1を便宜上置くと、次元が1つ減ってdpが簡単にできるようになるのかなり気持ち悪いと思います、思いませんか？

これ1000点じゃないだろ 問題概要 読んで: F - Candy Retribution 解法 条件を満たす昇順の列 に対して、それを並べる方法は通りある。 ここでは にが個含まれることを指す。 よって、dp[x][y] := 「y個からなる列を考えた時、それらの和はxとなっているもの…