potetisensei https://blog.hatena.ne.jp/potetisensei/ 生きたい https://potetisensei.hatenablog.com/ 想定解はフローだが、離散凸解析をちょっと知っていると、目的関数がM凸なので、交換を繰り返すと解けることが分かる。 実際、Benqは本番これで通しているらしい これを証明する。 問題文中で定義されている目的関数をfとする。これがM凸であることを示す。 まずfの定義域である、実行可能解の集合Sが整基集合（とりあえずM凸関数のステートメントが成立するような集合と考えていい）であることを示す。 ↑ノリでm+1にしたけどmでよかったな これはかなり雑、というかこの書き方だと、「対称性からy + e_i - e_jも実行可能解」が成立してないけど、1..nを頂点としたグラフ（辺は、数列の各要素kに関してL… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fpotetisensei.hatenablog.com%2Fentry%2F2020%2F07%2F12%2F212639" title="Educational Codeforces Round 29 F. Almost Permutation - 生きたい" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/p/potetisensei/20200712/20200712204017.png Hatena Blog https://hatena.blog 2020-07-12 21:26:39 rich https://potetisensei.hatenablog.com/entry/2020/07/12/212639 1.0 100%