Problem:


Score : 700 points

Problem Statement

We have N cards numbered 1, 2, ..., N.
Card i (1 \leq i \leq N) has an integer A_i written in red ink on one side and an integer B_i written in blue ink on the other side.
Initially, these cards are arranged from left to right in the order from Card 1 to Card N, with the red numbers facing up.

Determine whether it is possible to have a non-decreasing sequence facing up from left to right (that is, for each i (1 \leq i \leq N - 1), the integer facing up on the (i+1)-th card from the left is not less than the integer facing up on the i-th card from the left) by repeating the operation below. If the answer is yes, find the minimum number of operations required to achieve it.

Choose an integer i (1 \leq i \leq N - 1).
Swap the i-th and (i+1)-th cards from the left, then flip these two cards.

Constraints

1 \leq N \leq 18

1 \leq A_i, B_i \leq 50 (1 \leq i \leq N)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N
B_1 B_2 ... B_N

Output

If it is impossible to have a non-decreasing sequence, print -1.
If it is possible, print the minimum number of operations required to achieve it.

Sample Input 1

3
3 4 3
3 2 3

Sample Output 1

1

By doing the operation once with i = 1, we have a sequence [2, 3, 3] facing up, which is non-decreasing.

Sample Input 2

2
2 1
1 2

Sample Output 2

-1

After any number of operations, we have the sequence [2, 1] facing up, which is not non-decreasing.

Sample Input 3

4
1 2 3 4
5 6 7 8

Sample Output 3

0

No operation may be required.

Sample Input 4

5
28 15 22 43 31
20 22 43 33 32

Sample Output 4

-1

Sample Input 5

5
4 46 6 38 43
33 15 18 27 37

Sample Output 5

3



Sample input:
3
3 4 3
3 2 3


Sample output:
1

Submission status: Accepted

Solution code:
from itertools import combinations
n = int(input())
As = list(map(int, input().split()))
Bs = list(map(int, input().split()))

even = []   #偶数番目で表になる
odd = []    #奇数番目で表になる
for i,(a,b) in enumerate(zip(As,Bs)):
    if i%2 == 0:
        even.append(a)
        odd.append(b)
    else:
        even.append(b)
        odd.append(a)



def check(n, even, odd):
    prev = -10**10
    ps = []
    for i in range(n):
        if i%2 == 0:
            if prev > even[i//2][0]:
                return False,-1
            else:
                ps.append(even[i//2][1])
            prev = even[i//2][0]
        else:
            if prev > odd[i//2][0]:
                return  False, -1
            else:
                ps.append(odd[i//2][1])
            prev = odd[i//2][0]
    return True, ps
    


def inversion(a):
    n = len(a)
    cnt = 0
    for i in range(n):
        for j in range(i+1,n):
            if a[i] > a[j]:
                cnt +=1
    return cnt
 
#偶数としてpickupするやつ
INF = 10**10
ans = 10**10
for l in combinations(range(n), (n-1)//2+1):
    cnt = 0
    even_selected = [(even[i],i) for i in range(n) if i in l]
    odd_selected = [(odd[i],i) for i in range(n) if i not in l]
    # こいつらを昇順に並べられるか
    even_selected.sort()
    odd_selected.sort()
    is_possible, a = check(n, even_selected, odd_selected)
    # 並び順が正しければ
    if is_possible:
        cnt = inversion(a)
        ans = min(cnt, ans)
        
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N = int(readline())
A = list(map(int,readline().split()))
B = list(map(int,readline().split()))

class BinaryIndexedTree():
    def __init__(self, seq):
        self.size = len(seq)
        self.depth = self.size.bit_length()
        self.build(seq)
        
    def build(self,seq):
        data = seq
        size = self.size
        for i,x in enumerate(data):
            j = i+(i&(-i))
            if j < size:
                data[j] += data[i]
        self.data = data
        
    def __repr__(self):
        return self.data.__repr__()
        
    def get_sum(self,i):
        data = self.data
        s = 0
        while i:
            s += data[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        data = self.data
        size = self.size
        while i < size:
            data[i] += x
            i += i & -i
    
    def find_kth_element(self,k):
        data = self.data; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + data[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def Inversion(seq):
    # seqは、1,2,...,Nの順列
    N = len(seq)
    bit = BinaryIndexedTree([0] * (N+1))
    inv = N*(N-1)//2
    for x in seq:
        inv -= bit.get_sum(x)
        bit.add(x,1)
    return inv

INF = 10 ** 9
answer = INF
for I in itertools.combinations(range(N),(N+1)//2):
    J = [j for j in range(N) if j not in I]
    ODD = [(B[i] if i&1 else A[i],i) for i in I]
    EV = [(A[i] if i&1 else B[i],i) for i in J]
    ODD.sort()
    EV.sort()
    ind = [0] * N
    seq = [0] * N
    for i in range(0,N,2):
        seq[i], ind[i] = ODD[i//2]
    for i in range(1,N,2):
        seq[i], ind[i] = EV[i//2]
    if not all(x<= y for x,y in zip(seq,seq[1:])):
        continue
    ind = [x+1 for x in ind]
    n = Inversion(ind)
    if answer > n:
        answer = n

if answer == INF:
    answer = -1
print(answer)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL : https://atcoder.jp/contests/keyence2020/tasks/keyence2020_d
解説AC

きもすぎBit全探索および転倒数
    （転倒数に結びついたら強い
    　隣通しを入れ替えてsortの操作数→バブルソートの操作数→転倒数
    　これの徹底）

AC例1: 最初に考え付いたのはこっち
    maskでどのindexが裏返しになっているかを保持。
    その状況下で生成される表面の数の配列を作成し(これをLとする)ソート。
    iを[0,n)で回して各A[i],B[i]に対して
    maskをもとにAかBが使用されているかを見る。
    Lにおけるその数のindexとiの差の偶奇は奇数B偶数ならA。
    defalutdictかなんかで各Lの数字とそのindexの偶奇の数とそのindexを保持
    indexとiの差の偶奇とdictからLの各indexが元どの番号にいたかを保持。
    あとは元の番号の配列の転倒数を求めればそのmaskにおける操作数が出る

AC例2: 解説はこっち
    maskではどのindexがすでに左側で固定化されたかを保持。
    巡回セールスマンのようにどこを決めて最後に決めたindexは何か
    というDPでいける。（は？）
    というのもmaskだけではそのマスク内の順番はわからないからね。
    欲しいのはその固定化された物の最大の値なので最悪なんかうまくできるかも
    すごすぎ
    こっちを実装します
    700点をACしたいね(2020/3/25/ 20:05)

    Reference: https://atcoder.jp/contests/keyence2020/submissions/9567775 By:yutaka1999
"""

#solve
def solve():
    n = II()
    A = LI()
    B = LI()
    bit_length = [0] 
    for i in range(n):
        bit_length += [x + 1 for x in bit_length]
    dp = [[-1] * n for _ in range(1 << n)]
    for i in range(n):
        dp[1 << i][i] = 0
    for mask in range(1 << n):
        dpm = dp[mask]
        c = bit_length[mask]
        for i in range(n):
            if not((1 << i) & mask) or dpm[i] == -1: continue
            w = B[i] if 1 & i == c & 1 else A[i]
            cost = c
            for j in range(n):
                if 1 & (mask >> j):
                    cost -= 1
                else:
                    v = B[j] if 1 & j != c & 1 else A[j]
                    if v >= w:
                        vl = dpm[i] + cost
                        if dp[mask | (1 << j)][j] == -1 or dp[mask | (1 << j)][j] > vl:
                            dp[mask | (1 << j)][j] = vl

    ans = -1
    for i in range(n):
        if dp[-1][i] != -1:
            if ans == -1 or ans > dp[-1][i]:
                ans = dp[-1][i]
    print(ans)

    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
# reference -> https://atcoder.jp/contests/keyence2020/submissions/9649881
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 2**19

# dp[bit][s]
#   ビットに1が立っているカードはソートされて左から並んでいる
#   そのとき最後の値をsにするのに必要な最小操作回数
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1<<N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1<<N):
  num_used = bin(bit).count("1") # 既に並んでいるカードの枚数
  idx = num_used
  remaining = [] # まだ並べていないカードがどれか
  for i in range(N):
    if not (bit & (1 << i)):
      # (初期位置, 現在位置)
      #   - 初期位置 : 最初の状態で左から何番目にあるか
      #   - 現在位置 : bitで1が立っているカードを並べたときに左から何番目にあるか
      remaining.append((i, idx))
      idx += 1
  for s in range(51):
    # bitの集合かつ、その右端にsの状態が作れないならスキップ
    if dp[bit][s] >= INF:
        continue
    for init_pos, current_pos in remaining:
      # 最後尾まで移動させる際の交換回数に応じてA, Bの適切な方を選ぶ
      number = [A[init_pos], B[init_pos]][abs(init_pos-num_used)%2]
      if number >= s: # 現段階の最後尾の値以上であればOK
        dp[bit | (1<<init_pos)][number] = min(
          dp[bit | (1<<init_pos)][number], dp[bit][s] + abs(num_used - current_pos)
        )


# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min([dp[-1][s] for s in range(51)])

print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
#from collections import *
from itertools import *
#from bisect import *
#from heapq import *
#import copy
#N=int(input())
#X,Y=map(int,input().split())
#S=list(map(int,input().split()))
#S=[list(map(int,input().split())) for i in range(N)]
#import math

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
Zlst=set([i for i in range(N)])
if N==1:
    print(0)
    exit()
count=-1
for lst in combinations(range(N),N//2+N%2):
    odds=[[A[i],i] if i%2==0 else [B[i],i] for i in lst]
    even=[[B[i],i] if i%2==0 else [A[i],i] for i in list(Zlst-set(lst))]
    oddsst=sorted(odds,key=lambda  x:x[0])
    evenst=sorted(even,key=lambda  x:x[0])

    temp=oddsst[0][0]
    lst=[oddsst[0][1]]
    for i in range(1,N):
        if i%2==1:
            ntemp=evenst[i//2]
        else:
            ntemp=oddsst[i//2]
        if temp>ntemp[0]:
            flag=0
            break
        else:
            flag=1
            temp=ntemp[0]
            lst.append(ntemp[1])

    if flag:
        if count==-1:
            count=10**10
        tempcount=0
        while flag:
            flag=0
            for i in range(len(lst)-1):
                if lst[i]>lst[i+1]:
                    lst[i],lst[i+1]=lst[i+1],lst[i]
                    tempcount+=1
                    flag=1
        count=min(count,tempcount)


print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
def check(i):
  x = []
  for j in range(N):
    if i & (1 << j):
      x.append(b[j])
    else:
      x.append(a[j])
  sx = sorted(x)
  odd = [0] * 51
  even = [0] * 51
  for j in range(N):
    odd[sx[j]] += j % 2
    even[sx[j]] += (j % 2 == 0)
  for j in range(N):
    if i & (1 << j):
      if j % 2: even[x[j]] -= 1
      else: odd[x[j]] -= 1
    else:
      if j % 2: odd[x[j]] -= 1
      else: even[x[j]] -= 1
  return min(min(odd), min(even)) >= 0
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
res = float("inf")
for i in range(pow(2, N)):
  if check(i) == False: continue
  fwk = BIT(N)
  t = 0
  odd = []
  even = []
  for j in range(N):
    if i & (1 << j):
      if j % 2: even.append((b[j], j))
      else: odd.append((b[j], j))
    else:
      if j % 2: odd.append((a[j], j))
      else: even.append((a[j], j))
  #print(t, i)
  odd.sort(key = lambda x: x[0])
  even.sort(key = lambda x: x[0])
  ind = []
  #print(t, i)
  for j in range(N):
    if j % 2: ind.append(odd[j // 2][1])
    else: ind.append(even[j // 2][1])
  #print(t, i, ind)
  for x in ind:
    t += fwk.get(x, N)
    fwk.add(x + 1, 1)
  res = min(res, t)
  #print(t, i)
if res == float("inf"): print(-1)
else: print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res


def inv_cnt(seq):
    n = len(seq)
    bit = BIT(n)
    cnt = 0
    for i in range(n - 1, -1, -1):
        cnt += bit.sum(seq[i] - 1)
        bit.add(seq[i], 1)
    return cnt


n = I()
A = LI()
B = LI()
ans = INF
for odd_ind in combinations(range(n), n // 2):
    even_ind = set(range(n)) - set(odd_ind)
    odd_list = []
    even_list = []
    whole_num_list = []
    whole_idx_list = []
    for i in odd_ind:
        if i % 2:
            odd_list += [(A[i], i)]
        else:
            odd_list += [(B[i], i)]
    for j in even_ind:
        if j % 2:
            even_list += [(B[j], j)]
        else:
            even_list += [(A[j], j)]
    even_list.sort(reverse=1)
    odd_list.sort(reverse=1)
    while even_list or odd_list:
        x, idx = even_list.pop()
        whole_num_list += [x]
        whole_idx_list += [idx]
        if odd_list:
            x, idx = odd_list.pop()
            whole_num_list += [x]
            whole_idx_list += [idx]
    if whole_num_list == sorted(whole_num_list):
        ans = min(ans, inv_cnt(whole_idx_list))

if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = LI()
B = LI()
ans = INF
for odd_ind in combinations(range(n), n // 2):
    even_ind = set(range(n)) - set(odd_ind)
    odd_list = []
    even_list = []
    whole_num_list = []
    whole_idx_list = []
    for i in odd_ind:
        if i % 2:
            odd_list += [(A[i], i)]
        else:
            odd_list += [(B[i], i)]
    for j in even_ind:
        if j % 2:
            even_list += [(B[j], j)]
        else:
            even_list += [(A[j], j)]
    even_list.sort(reverse=1)
    odd_list.sort(reverse=1)
    while even_list or odd_list:
        x, idx = even_list.pop()
        whole_num_list += [x]
        whole_idx_list += [idx]
        if odd_list:
            x, idx = odd_list.pop()
            whole_num_list += [x]
            whole_idx_list += [idx]
    if whole_num_list == sorted(whole_num_list):
        cnt = 0
        for i in range(n):
            for j in range(i + 1, n):
                if whole_idx_list[i] > whole_idx_list[j]:
                    cnt += 1
        ans = min(ans, cnt)


if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:
from itertools import combinations
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))

def inversion(inds):
    bit = [0] * (N+1)
    def bit_add(x,w):
        while x <= N:
            bit[x] += w
            x += (x & -x)
    def bit_sum(x):
        ret = 0
        while x > 0:
            ret += bit[x]
            x -= (x & -x)
        return ret
    inv = 0
    for ind in reversed(inds):
        inv += bit_sum(ind + 1)
        bit_add(ind + 1, 1)
    return inv

INF = float('inf')
ans = INF
for odd_idxs in combinations(range(N), N//2):
    odd_idxset = set(odd_idxs)
    odds = []
    evens = []
    for i in range(N):
        if i in odd_idxset:
            odds.append((A[i] if i%2 else B[i], i))
        else:
            evens.append((B[i] if i%2 else A[i], i))
    odds.sort()
    evens.sort()
    vals = []
    inds = []
    for (e,ei),(o,oi) in zip(evens, odds):
        vals.append(e)
        vals.append(o)
        inds.append(ei)
        inds.append(oi)
    if len(evens) > len(odds):
        v,i = evens[-1]
        vals.append(v)
        inds.append(i)
    if any(a>b for a,b in zip(vals,vals[1:])): continue
    ans = min(ans, inversion(inds))

print(-1 if ans==INF else ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

@mt
def slv(N, A, B):
    AB = list(zip(A, B))


    ans = INF
    for f in product(range(2), repeat=N):
        o = []
        e = []
        for i, (c, ab) in enumerate(zip(f, AB)):
            v = ab[c]
            if i % 2 == 0:
                if c == 0:
                    e.append((v, i))
                else:
                    o.append((v, i))
            else:
                if f[i] == 0:
                    o.append((v, i))
                else:
                    e.append((v, i))
        if 0 <= len(e) - len(o) <= 1:
            bit = Bit(50)
            e.sort()
            o.sort()
            eo = [e, o]
            cand = 0
            p = -1
            for i in range(N):
                if p > eo[i%2][i//2][0]:
                    break
                p = eo[i % 2][i//2][0]
                bit.add(eo[i%2][i//2][1]+1, 1)
                cand += i + 1 - bit.sum(eo[i%2][i//2][1]+1)
            else:
                ans = min(ans, cand)
    if ans == INF:
        ans = -1
    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(slv(N, A, B))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]

all_cards = []
for i, (aa, bb) in enumerate(zip(a, b)):
    if i % 2:
        aa, bb = bb, aa
    all_cards.append([aa, bb, i])

def cnt(l):
    ret = 0
    for i in range(len(l)-1):
        for j in range(i+1, len(l)):
            if l[i][1] > l[j][1]:
                ret += 1
    return ret

ans = float('inf')
for cards in combinations(all_cards, (n + 1)// 2):
    acards = []
    for card in cards:
        acards.append([card[0],card[2]])
    bcards = []
    for card in all_cards:
        if [card[0],card[2]] not in acards:
            bcards.append([card[1],card[2]])

    acards.sort()
    bcards.sort()
    abcards = []
    # print(acards, bcards)
    for i in range(len(bcards)):
        abcards.extend([acards[i], bcards[i]])
    else:
        if n % 2:
            abcards.append(acards[-1])
    # print(abcards)
    if abcards != sorted(abcards, key=lambda x: x[0]):
        continue
    ans = min(ans, cnt(abcards))

if ans == float('inf'):
    ans = -1
print(ans)

Submission status: Accepted

Solution code:



N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 20

# bitで１が立っているidxのカードがソートされて左詰めで並んでいるとき、その右端（＝最大のカード）がsとなる最小コスト
dp = [[INF for _ in range(51)] for _ in range(1 << N)]
dp[0][0] = 0

for bit in range(1 << N):

    # 既に並べてあるカードの枚数
    num_used = bin(bit).count("1")

    curr = num_used
    remaining = []
    for i in range(N):
        # bitのi番目に１が立っていない（＝まだ選ばれていない）とき
        if not(bit & (1 << i)):
            remaining.append((i, curr))
            curr += 1

    for s in range(51):
        # あるカードの並べ方について、右端をsにできないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            # iniの場所に最初いたカードを、num_usedの位置に持ってくるので、その偶奇によって表か裏かがわかる
            num = A[ini] if abs(num_used - ini) % 2 == 0 else B[ini]

            # numがsより小さい場合、整列したカードの最後尾につけられない
            if num >= s:
                # ある選び方で並んでいるカード群に、ini番目のカードを新たに最後尾に追加したとき、最後尾がnumとなる最小コスト
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))

ans = INF
for i in range(51):
    ans = min(ans, dp[-1][i])

print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:
from itertools import combinations

def solve():
    INF = 10**5

    def getNumInversion(odrAs):
        def makeBIT(numEle):
            numPow2 = 2 ** (numEle-1).bit_length()
            data = [0] * (numPow2+1)
            return data, numPow2
        def addValue(iA, A):
            iB = iA + 1
            while iB <= numPow2:
                data[iB] += A
                iB += iB & -iB
        def getSum(iA):
            iB = iA + 1
            ans = 0
            while iB > 0:
                ans += data[iB]
                iB -= iB & -iB
            return ans
        lenA = len(odrAs)
        data, numPow2 = makeBIT(lenA)
        ans = 0
        for odrA in reversed(odrAs):
            ans += getSum(odrA)
            addValue(odrA, 1)
        return ans

    N = int(input())
    As = list(map(int, input().split()))
    Bs = list(map(int, input().split()))

    ans = INF
    for iEvens in combinations(range(N), r=N//2):
        iEvens = set(iEvens)
        COdds, CEvens = [], []
        for i in range(N):
            if i in iEvens:
                if i % 2:
                    CEvens.append((As[i], i))
                else:
                    CEvens.append((Bs[i], i))
            else:
                if i % 2:
                    COdds.append((Bs[i], i))
                else:
                    COdds.append((As[i], i))
        COdds.sort()
        CEvens.sort()

        Cs = []
        for COdd, CEven in zip(COdds, CEvens):
            Cs += [COdd, CEven]
        if N % 2:
            Cs += [COdds[-1]]

        for i in range(N-1):
            if Cs[i][0] > Cs[i+1][0]:
                break
        else:
            odrAs = [i for C, i in Cs]
            num = getNumInversion(odrAs)
            ans = min(ans, num)
            if ans == 0:
                break

    if ans == INF:
        print(-1)
    else:
        print(ans)


solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def pop_count(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
cards = [[]] * 2
cards[0] = LIST()
cards[1] = LIST()

ans = INF
for S in range(1<<N):
    # 無理なケース(奇数枚裏返す)を除外
    if pop_count(S) % 2 != 0:
        continue
    # 奇数位置と偶数位置で分けて保持する
    A1 = [[] for i in range(2)]
    for i in range(N):
        # カードiを青くする
        if S & 1<<i:
            A1[(i&1)^1].append((cards[1][i], i))
        # 赤のまま
        else:
            A1[i&1].append((cards[0][i], i))
    # 無理なケース(置きたい偶奇位置の数がおかしい)を除外
    if len(A1[0]) != ceil(N, 2) or len(A1[1]) != N // 2:
        continue
    # 偶奇が同じ位置同士は自由に動けるのでソートする
    A1[0].sort(reverse=1)
    A1[1].sort(reverse=1)
    cnt = 0
    A2 = [0] * N
    idxs = [0] * N
    for i in range(N):
        # 偶奇位置を交互に取り出す
        A2[i], idxs[i] = A1[i&1].pop()
    # ソート済と一致すればOK
    if A2 == sorted(A2):
        # 移動距離を転倒数数え上げで求める(Nが小さいのでN^2かけて大丈夫)
        cnt = 0
        for i, idx1 in enumerate(idxs):
            for j, idx2 in enumerate(idxs[i+1:], i+1):
                if idx1 > idx2:
                    cnt += 1
        ans = min(ans, cnt)
if ans == INF:
    print(-1)
else:
    print(ans)

Submission status: Accepted

Solution code:


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 19

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)

Submission status: Accepted

Solution code:


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

INF = 1 << 29

"""
・dp[bit][s]
ビットに1が立っているカードはソートされて左から並んでいる。
そのとき最後の値をsにするのに必要な最小操作回数


"""
# 1 <= A,B <= 50, bitの立ち方が 0...0 ~ 1...1 の2**N
dp = [[INF for _ in range(50 + 1)] for _ in range((1 << N))]
# 0枚選んでいて右端が0は何もしてないのでコスト0
dp[0][0] = 0

for bit in range(1 << N):
    # 現在見ているbit列にいくつ1が立っているか＝カードを何枚既に選んで並べているか
    num_used = bin(bit).count("1")
    
    # bitで１が立っていない＝まだ使われていないカードがどこにあるか
    idx = num_used
    remaining = []
    for i in range(N):
        if not (bit & (1 << i)):
            # 一つ目が初期位置、二つ目は、bitで１が立っているやつらを左に寄せた時にどの位置にいるか
            remaining.append((i, idx))
            idx += 1

    for s in range(51):
        # bitの集合かつ、その右端にsの状態が作れないならスキップ
        if dp[bit][s] >= INF:
            continue

        for ini, curr in remaining:
            """
            ini  : initial position
            curr : current position
            現時点でnum_used-1のインデックスまでカードがソートされて並んでいる
            最初iniの位置にあったカードを最後尾に並べることを考える
            """
            num = A[ini] if abs(ini - num_used) % 2 == 0 else B[ini]

            """
            numが並んでるカードの最後尾より大きければ最後尾につける
            """
            if num >= s:
                # 元の集合と、iniの位置だけ１が立ってるものの論理和で、追加した状態を表す
                # その場合の最小コストは、既に求まっているもの or 新たにnum_usedの位置にiniのカードをあてたとき　の小さいほう
                dp[bit | (1 << ini)][num] = min(dp[bit | (1 << ini)][num], dp[bit][s] + abs(num_used - curr))



# 全てのbitに1が立っている（全て並べ切った）時の最小コストが答え
ans = min(dp[-1][s] for s in range(51))

print(ans if ans < INF else -1)