Quiz

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

AC

https://atcoder.jp/contests/keyence2020/submissions/9586830

解法

i番目が表か裏かをbit全探索
表裏を決めた時につじつまが合っているかチェック
チェックを通ったなら、最終的なincreasing列が決まり、反転数が決まり、そのminをとればいい

有用そうなテストケース

5
38 19 17 7 31
31 49 25 42 6

f:id:peroon:20200119144236p:plain

質問「値の配列から反転数を求めるのではダメ？」

Answer : ダメです
上の例のように同じ値が存在する場合にダメになる場合がある
元々の列＝[31, 19, 17, 42, 31] (赤丸)
作りたい列 = [17, 19, 31, 31, 42]
これを普通にバブルソートして反転数を求めると、4であり、答えの5と合わない
これは、0, 1のフラグにより各値が行ける位置の偶奇が決まっているからである
下記画像のように遠くに移動する必要があり、その時の移動回数を求める必要がある
- なので移動距離は4ではなく5

f:id:peroon:20200119032528j:plain

Code (mainのみ)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin >> N;

    VI A(N);
    rep(i, N) cin>>A[i];

    VI B(N);
    rep(i, N) cin>>B[i];

    ll mi = inf;
    ll odd = N/2;
    ll even = N-odd;
    rep(f, 1LL<<N){
      vector<PII> OD; // odd vector // {val, index}のリスト
      vector<PII> EV; // even vector // 〃
      rep(i, N){
        if(f>>i&1){
          // 1だとひっくり返ってるとする
          if(i%2==0){
            OD.push_back(MP(B[i], i));
          }else{
            EV.push_back(MP(B[i], i));
          }
        }else{
          if(i%2==0){
            EV.push_back(MP(A[i], i));
          }else{
            OD.push_back(MP(A[i], i));
          }
        }
      }
      if(odd==SZ(OD) && even==SZ(EV)){
        // ok
      }else{
        // debug("skip by size");
        continue;
      }

      // odd, evenの数は合っている
      SORT(EV);
      SORT(OD);
      // zip (合成する)
      vector<PII> SO; // sorted vector
      rep(i, SZ(OD)){
        SO.push_back(EV[i]);
        SO.push_back(OD[i]);
      }
      if(SZ(EV)!=SZ(OD)){
        SO.push_back(EV.back());
      }

      // これがsortedかチェック
      if(isIncreasing2(SO)){
        // ok
      }else{
        // debug("skip by not sorted");
        continue;
      }

      // original vectorをsortedにするまでの回数が反転数
      VI I;
      for(auto pa : SO){
        I.push_back(pa.second);
      }
      
      ll h = bubble_sort(I);
      chmin(mi, h);
    }

    if(mi==inf){
      p(-1);
    }else{
      p(mi);
    }
    
    return 0;
}