キーエンスプログラミングコンテスト 2020 D - Swap and Flip

お題箱より。

解法

この問題のように「操作する場所を選んで、決められたルールに従って操作する」ということを繰り返す問題では、1回目の操作の選択、2回目の操作の選択…といった分岐パターンを直接探索していくのは非常に大変です。操作の途中過程を考えなくて良いような戦略をいかに立てるかが重要です。例えば、

操作の過程に関わらず、常に成り立っている性質や不変な量が存在する。
最終状態だけが分かれば、操作の過程を考えなくても、操作について求めたい値（最小の操作回数や操作コストの合計値、その最終状態が実現できるかどうかのYes/No判定など）が分かる方法が存在する。

というような嬉しい性質がないかを考察してみましょう。

考察1

「隣り合う2枚のカードを選び、位置を入れ替え、それぞれ裏返す」という操作の特徴を考察します。どのカードも位置が1つ移動するごとに表裏が入れ替わるので、元々あった位置と最終的な位置の差（移動距離）が偶数ならば表向き、奇数ならば裏向きになります。これはつまり、どのような操作過程を辿ったとしても、最後の各カードの位置を決めれば全てのカードの向きが一意に決まることを意味します。

考察2

最後の各カードの位置を決めたとします。初期状態からその位置に並べ替えるための操作回数の最小値は、各カードの番号（＝初期位置の並び順）を最後の位置に並べてできる順列の転倒数という値になります。すなわち「2つのカード番号 $(i, j)$ の組であって、 $i \lt j$ かつカード $i$ よりもカード $j$ のほうが左にあるものの個数」です。

転倒数の求め方として、左から順番に要素を見ていきながら「自身より左側に登場済みで、かつ自身より小さい要素」の個数を合計していくという方法があります。図のように今見ている要素を $i$ 、左側に登場済みで $i$ より大きい要素を $j$ とすると、組 $(i, j)$ は先ほどの条件を満たします。これを合計していくことで転倒数を求めることができるため、各ステップでは既に登場した要素の集合だけを覚えておけば転倒数の増加分を計算することができます。

f:id:betrue12:20200917185311p:plain

DPを組む

ここまでの考察を使って答えを求める方法を考えます。考察1、2で確認したように操作の途中経過については考える必要がないので、最終状態の並び順をいきなり考えてしまって良いです。

$N$ が小さいことから、「今までどのカードを置いたか」の集合を持ちながら1つずつ順に置くカードを決めていく、いわゆるbit DPを考えることができます。左から順番に置くカードを決めていくとすると、必要な情報は

今までどのカードを置いたか？
最後に置かれたカードはどれか？
そこまでの転倒数はいくつか？

の3点です。以下のようにDPの状態を定義します。

$dp\lbrack s \rbrack\lbrack x\rbrack =$ 既に置いたカードの集合が $s$ であって、最後に置かれたカードが $x$ で、既に置いたカードの表向きになっている値は広義単調増加になっているときの、そこまでの転倒数の最小値

$dp\lbrack s \rbrack\lbrack x\rbrack$ からの遷移として、次に置くカードの候補 $y$ を全て試します。このとき調べる必要があるのは

単調増加性は守られるか？（＝その遷移をしてもよいか？）
転倒数はいくつ増加するか？

の2点です。単調増加性については考察1より、最後に置かれたカード $x$ と次に置くカード $y$ の向きが移動距離の偶奇から決まるので実際に値を比較して判定できます。転倒数の増加分については考察2より、既に置かれたカードの集合 $s$ の中で $y$ よりも番号の大きいものを数えれば良いです。遷移先は $dp\lbrack s\cup \lbrace y\rbrace \rbrack\lbrack y\rbrack$ で、bit DPの代表例として紹介される巡回セールスマン問題に似た実装をすることになります。

このDPを計算し終わったら、カード全体の集合を $U=\lbrace 1, 2, ..., N\rbrace$ として、 $\min_{x} dp\lbrack U \rbrack\lbrack x\rbrack$ が答えです。

ACコード

Submission #9569271 - Keyence Programming Contest 2020

時間計算量は $O(N^{2}2^{N})$ です。転倒数の増加分を計算する時に毎回全要素を見ていると $O(N^{3}2^{N})$ になるので少し工夫しましょう。予め全ての $(s, y)$ に対して「集合 $s$ の中で $y$ よりも番号の大きいものの個数」を前計算しても良いですし、上記リンク先のコードでは次に置くカード $y$ を小さい番号から順に見ていきながら、増加分の変化を管理しています。