問題概要

表に $A_{i}$ 、裏に $B_{i}$ と書かれた $N$ 枚のカードが一列に並んでいる。以下の操作を繰り返すことで、表に出ているカードが広義単調増加となるようにしたい。最小回数を求めよ。

隣り合う 2 枚のカードを選んで swap し、ともに裏返す

制約

$1 \le N \le 18$
$1 \le A_{i}, B_{i} \le 50$

考えたこと

操作がわかりづらいけど、もともと i 番目にあったカードが最終的に j 番目に移動するとき

| i - j | が偶数ならば、表の数値は A[ i ]
| i - j | が奇数ならば、表の数値は B[ i ]

になるというイメージ。これを踏まえて、最終的な位置がどうなるべきなのかを求めていくことになる。

そして、この手の隣接 swap 系の問題は、似た雰囲気の DP でできることが多い。今回は

dp[ bit ][ s ] := $N$ 枚のカードのうち、bit で表されるものについては左詰めしてソートされている状態で、最後の値が $s$ である状態にするまでに必要な操作回数

注意点として、bit の中身が $c$ 枚であるとき、bit で表されないカードについては、 $c+1$ 番目以降に配置され直されることになる。なので、dp[ bit ][ s ] の状態で、bit に含まれないカードがそれぞれ何番目に対応するのかを対応付ける必要がある。

dp[ bit ][ s ] に新たに i 番目のカードを加えるとき、そのカードの現在地が p 番目であるとして、

chmin( dp[ bit | (1 << i) ][ t ], dp[ bit ][ s ] + abs(c - p) )

という感じになる。t の部分は、

| i - c | が偶数のときは A[ i ]
| i - c | が奇数のときは B[ i ]

ということになる。t の値が s よりも小さい場合は遷移しない。ここでは $s$ は絶対値を用いているけど、実際は $2N$ 種類の値に用いることができる。その場合、計算量は $O(N^{2}2^{N})$ になる。

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pint = pair<int,int>;
const int INF = 1<<29;

int N;
vector<int> A, B;

int solve() {
    vector<vector<int>> dp((1<<N)+1, vector<int>(55, INF));
    dp[0][0] = 0;
    for (int bit = 0; bit < (1<<N); ++bit) {
        int con = 0;
        for (int i = 0; i < N; ++i) if (bit & (1<<i)) ++con;
        
        // bit に含まれない残りの要素が何番目に対応するか
        vector<pint> ords;
        int iter = con;
        for (int i = 0; i < N; ++i)
            if (!(bit & (1<<i)))
                ords.emplace_back(i, iter++);

        for (int s = 0; s <= 50; ++s) {
            if (dp[bit][s] >= INF) continue;
            for (auto p : ords) {
                // p.first: もともとの a の index
                // p.second: dp[bit][s] の状態での index
                int ns = -1;
                if (abs(p.first - con) % 2 == 0) ns = A[p.first];
                else ns = B[p.first];

                if (ns >= s) {
                    chmin(dp[bit|(1<<p.first)][ns], dp[bit][s] + abs(p.second - con));
                }
            }
        }
    }
    int res = INF;
    for (int s = 0; s <= 50; ++s) chmin(res, dp[(1<<N)-1][s]);
    if (res < INF) return res;
    else return -1;
}

int main() {
    cin >> N;
    A.resize(N), B.resize(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) cin >> B[i];
    cout << solve() << endl;
}