ferinの競プロ帳

競プロについてのメモ

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

問題ページ

0-originで考えます.

制約からメタ読みするとどうせ O(2^n) かけて列挙するので,並べ替えた後の列で表が赤になるカードの集合を O(2^n) 通りを決め打ちます.「このような並べ方が存在するか?存在するならば何回のswapで達成可能か?」という問題が解ければよいことになります.

並べ方が存在するか?

元の列の位置の偶奇と並べ替えた後の列の偶奇が

  • 一致する: 赤が表
  • 一致しない: 青が表

となります.したがって,各数字が偶数/奇数番目に来る個数が何個になっていればokな並べ方か?ということを求めることができます.実際に a_i, b_i を並べ,ソートした列と比較することで判定が可能です.

swapは何回か?

隣接する2項のswapで求める列をつくる回数は,ようするに転倒数です.並べ替えた後,i 番目のカードがどこに行くのか?は実際にソートすればわかるので,あとは O(n^2) かけて転倒数を求めればよいです.

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n), b(n);  
    REP(i, n) cin >> a[i], a[i]--;  
    REP(i, n) cin >> b[i], b[i]--;  
  
    ll ret = INF;  
    REP(i, 1LL<<n) {  
        vector<ll> v;  
        vector<PII> need(50), v0, v1;  
        REP(j, n) {  
            if(i&1LL<<j) {  
                v.push_back(a[j]);  
                if(j%2==0) {  
                    need[a[j]].first++;  
                    v0.push_back({a[j], j});  
                }  
                else {  
                    need[a[j]].second++;  
                    v1.push_back({a[j], j});  
                }  
            }  
            else {  
                v.push_back(b[j]);  
                if(j%2==0) {  
                    need[b[j]].second++;  
                    v1.push_back({b[j], j});  
                }  
                else {  
                    need[b[j]].first++;  
                    v0.push_back({b[j], j});  
                }  
            }  
        }  
        sort(ALL(v));  
        vector<PII> vp(50);  
        REP(j, n) {  
            if(j%2==0) vp[v[j]].first++;  
            else vp[v[j]].second++;  
        }  
        if(need != vp) continue;  
  
        // 何手かかるか?  
        sort(ALL(v0));  
        sort(ALL(v1));  
        vector<ll> sorted;  
        REP(i, max(v0.size(), v1.size())) {  
            if(i < v0.size()) sorted.push_back(v0[i].second);  
            if(i < v1.size()) sorted.push_back(v1[i].second);  
        }  
        dump(bitset<3>(i));  
        dump(sorted);  
  
        ll tmp = 0;  
        vector<ll> num(n);  
        REP(j, n) {  
            FOR(k, sorted[j], n) {  
                tmp += num[k];  
            }  
            num[sorted[j]]++;  
        }  
        chmin(ret, tmp);  
    }  
  
    if(ret == INF) cout << -1 << endl;  
    else cout << ret << endl;  
  
    return 0;  
}