キーエンスコン2020 D Swap and Flip

キーエンスコン2020 D Swap and Flip

問題概要

リンク参照

問題リンク

https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d

考察

制約がbitDPしてほしそうな制約をしている
$:i$ 番目の値が動いた時，表と裏どちらになるのか見てあげると $:i$ 番目から $:j$ 番目に動くときに $:i-j$ が奇数なら裏，偶数なら表を使うことになる

dp[msk][lst]：既に単調増加になっているものの状態がmskで最後に使った数字がlstであるときの操作回数する
mskの立っているbit数が $:k$ 個の時，既に小さい方から $:k$ 番目の数字は確定しているので，次の数字は $:k+1$ 番目の数字になる

ソースコード

#include<algorithm>
#include<bitset>
#include<cassert>
#include<cfloat>
#include<climits>
#include<cmath>
#include<deque>
#include<functional>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<array>
#include<set>
#include<stack>
#include<string>
#include<unordered_map>
#include<unordered_set>
#include<utility>
#include<vector>

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;


template<typename T>
vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
	return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template<typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type
fill_v(T& t, const V& v) { t = v; }
template<typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type
fill_v(T& t, const V& v) {
	for (auto& e : t) fill_v(e, v);
}


template <typename T>
bool chmax(T & a, const T & b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template <typename T>
bool chmin(T & a, const T & b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}


const int INF = 1e9 + 7;
constexpr ll MOD = 1e9 + 7;

/******************************************************************************************/


int dp[(1<<18)][55];

int main() {

	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(10);

    int N;
    cin >> N;
    auto AB = make_v<int>(2,N);
    for(int i = 0;i < 2;i++){
        for(int j = 0;j < N;j++){
            cin >> AB[i][j];
        }
    }
    
    for(int i = 0;i < (1<<18);i++){
        for(int j = 0;j < 55;j++){
            dp[i][j] = INF;
        }
    }

    dp[0][0] = 0;
    for(int msk = 0;msk < (1<<N);msk++){

        for(int lst=0;lst <= 50;lst++){
            if(dp[msk][lst]==INF)continue;

            int done = 0;
            for(int i= 0;i < N;i++){
                if((msk>>i)&1)done++;
            }
            for(int i = 0;i < N;i++){

                if((msk>>i)&1)continue;

                int nxt = AB[abs(done-i)%2][i];

                if(nxt < lst)continue;

                int c = 0;
                for(int j = 0;j < i;j++){
                    if(!((msk>>j)&1))c++;
                }
                chmin(dp[msk|(1<<i)][nxt],dp[msk][lst]+c);
            }
        }
    }

    int ans = INF;
    for(int i = 0;i < 51;i++){
        chmin(ans,dp[(1<<N)-1][i]);
    }
    if(ans == INF)ans=-1;
    cout << ans << endl;





	return 0;
}