drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ Codeforces 順列を題材とした問題 操作 データ構造 セグメント木 データ構造テク：全体に反映させる値を別にもつ(遅延評価) StarrySkyTree データ構造テク：差分更新 考察：一部の変数を固定して考える in-place DP DP 最小コスト CodeforcesR2200 EducationalCodeforces 遅延評価セグメント木 最適化問題 これを思い出して迷走してしまった (それでも通る解法には至ったけど恐ろしく煩雑なものとなってしまった)。 drken1215.hatenablog.com なぜもっとシンプルに考えられなかったのか... 問題へのリンク 問題概要 の順列 と、各要素 を動かすのに必要なコスト が与えられる ( は index の要素を動かすコストではなく、要素 を動かすコスト)。 今、順列を左右に分ける。左右はそれぞれ empty ではないようにする。このとき、左の要素を選んで右に動かしたり、右の要素を選んで左に動かしたりすることで、「左側のどの要素も右側のどの要素よりも小さい」という状態を達成したい。 それに… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F01%2F30%2F132200" title="Educational Codeforces Round 81 E. Permutation Separation (R2200) - けんちょんの競プロ精進記録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%201%2C%202%2C%20%5Cdots%2C%20N Hatena Blog https://hatena.blog 2020-01-30 13:22:00 rich https://drken1215.hatenablog.com/entry/2020/01/30/132200 1.0 100%