drken1215 https://blog.hatena.ne.jp/drken1215/ けんちょんの競プロ精進記録 https://drken1215.hatenablog.com/ AtCoder AtCoder700点 DP 操作:隣接swap 操作:swap 操作 最小回数・最小個数を求める 考察：一部の変数を固定して考える 転倒数 BIT bitDP 考察：パリティに着目する 考察：操作・条件・目的関数を言い換える 青色diff ARC-like DP状態:吸い出しと吸い込み DP状態:ビット スライドbitDP 要素の並び替えを管理するDP 最適化問題 隣接 swap 操作を行いながら最小回数でソートする系の問題は、過去に何度も出てる！！！ drken1215.hatenablog.com drken1215.hatenablog.com これらはいずれも自然に DP で解くことができる。今回も。なお、「どれを表にするかを決め打って転倒数を求める」という方法もあるっぽい。 問題へのリンク 問題概要 表に 、裏に と書かれた 枚のカードが一列に並んでいる。以下の操作を繰り返すことで、表に出ているカードが広義単調増加となるようにしたい。最小回数を求めよ。 隣り合う 2 枚のカードを選んで swap し、ともに裏返す 制約 考えたこと 操作がわかり… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdrken1215.hatenablog.com%2Fentry%2F2020%2F01%2F19%2F025500" title="キーエンス プログラミング コンテスト 2020 D - Swap and Flip (青色, 700 点) - けんちょんの競プロ精進記録" 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.user.blog.st-hatena.com/default_entry_og_image/80936665/1687765056723440 Hatena Blog https://hatena.blog 2020-01-19 02:55:00 rich https://drken1215.hatenablog.com/entry/2020/01/19/025500 1.0 100%