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

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f

問題概要

$N ( \leq 18)$ 枚のカードがあり，左から $i$ 枚目のカードは表に $A_i (\leq 100)$，裏に$B_i (\leq 100)$ が書いてある。次の操作のみを行い，カードが左から右に広義単調増加になるように並べることができるだろうか。できるならば最小の操作回数を答えよ。

整数 $i (\leq N-1)$ を1つ選び， $i$ 枚目のカードと $i+1$ 枚目のカードの位置を交換する。その後，その2枚のカードを裏返す。

解法概要

swap に加えて flip も行われるのでややこしいが，カードの裏表に関しては

最終的な場所の index と最初の index の差が偶数なら表
最終的な場所の index と最初の index の差が奇数なら裏

といえる (1つ動くたびに裏表が逆になるので)。

また，裏表については，1回の操作で

表になっている2枚のカードが裏になる
表と裏のカード1枚ずつがそれぞれ裏と表になる
裏になっている2枚のカードが表になる

しかないので，裏返されているカードは常に偶数枚になる。

仮に，最終的なカードの裏表がすべてのカードについて決まっているとする。上記の考察より，最終的な裏表と最初の index の偶奇から「最終的なカードの index の偶奇」がわかる。より具体的には，

最初の index は偶数，最終的に表になるカードは最終的な index も偶数
最初の index は偶数，最終的に裏になるカードは最終的な index は奇数
最初の index は奇数，最終的に表になるカードは最終的な index も奇数
最初の index は奇数，最終的に裏になるカードは最終的な index は偶数

となる。

最終的な index の偶奇ごとに (見えている値, 元々の index) を格納した vector を作ると，後はソートして交互に組み合わせれば操作後の数列ができる。操作後の数列を作っている最中に最終的な index が偶数 / 奇数になる数のいずれかが枯渇したら，その裏表の組み合わせでは広義単調増加列はできない。特に数が枯渇することもなく広義単調増加列を作れる場合は，できた数列の要素それぞれの元々の index を格納した新しい数列を作り，それに対して転倒数を求めれば操作回数が求まる。

今回は $N$ が18以下と小さいので，すべてのカードの裏表の組み合わせ $2^N$ 通りをすべて試すことができる。$2^N$ 通りすべてについて操作回数を計算し，最小の操作数を答えればよい。

時間計算量は $\mathcal{O}(2^N N \log (\max(N, A_\mathrm{max}, B_\mathrm{max})))$……なのかな？

ソースコード

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

using namespace std;

using Pii = pair<int, int>;

constexpr int INF = 1 << 30;

template<typename T>class BIT {
    public:
    int n;
    vector<T> bit;
    
    BIT(int n): n(n){
        bit.resize(n);
        fill(bit.begin(), bit.end(), (T)0);
    }

    void add(int idx, T x){
        for(int i=idx;i<=this->n;i+=i&-i) bit[i] += x;
    }

    //bit[1]からbit[end]までの和 (閉区間)
    T sum(int end){
        T ret = (T)0;
        for(int i=end;i>=1;i-=i&-i) ret += bit[i];
        return ret;
    }

    T count_swap(vector<int> &v){
        T ret = (T)0;
        int m = v.size();
        for(int i=1;i<=m;++i){
            add(v[i-1], 1);
            ret += i - sum(v[i-1]);
        }
        return ret;
    }
};


int main() {
    int n;
    cin >> n;
    vector<Pii> a(n);
    for(int i=0;i<n;++i) cin >> a[i].first;
    for(int i=0;i<n;++i) cin >> a[i].second;

    int ans = INF;
    for(unsigned int bi=0;bi<(1<<n);++bi) { // カードを裏返す/裏返さないの組み合わせ
        if(__builtin_popcount(bi) % 2) continue; // 裏返っているカードの数が奇数にはならない

        vector<Pii> v[2];   // v[0]: 偶数番目に配置されるべきカード, v[1]: 奇数番目に配置されるべきカード
        {
            vector<Pii> tmp_v(n);
            for(int i=0;i<n;++i) {
                if(bi & (1 << i)) {
                    v[1-i%2].emplace_back(a[i].second, i);
                } else {
                    v[i%2].emplace_back(a[i].first, i);
                }
            }
            sort(v[0].begin(), v[0].end());
            sort(v[1].begin(), v[1].end());
        }

        bool is_ok = true;
        int prev_v = -1;
        vector<int> u(n);
        for(int i=0;i<n;++i) {
            if(i/2 >= v[i%2].size() || prev_v > v[i%2][i/2].first) {
                is_ok = false;
                break;
            }
            prev_v = v[i%2][i/2].first;
            u[i] = v[i%2][i/2].second + 1;
        }
        if(!is_ok) continue;

        BIT<int> tree(100);
        ans = min(ans, tree.count_swap(u));
    }

    cout << ((ans == INF)?-1:ans) << endl;
}

所感

解説とは違う解法で解いたみたい。