Problem:


Score : 600 points

Problem Statement

There are 2N balls, N white and N black, arranged in a row. The integers from 1 through N are written on the white balls, one on each ball, and they are also written on the black balls, one on each ball.
The integer written on the i-th ball from the left (1 ≤ i ≤ 2N) is a_i, and the color of this ball is represented by a letter c_i.
c_i = W represents the ball is white; c_i = B represents the ball is black.

Takahashi the human wants to achieve the following objective:

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the white ball with i written on it is to the left of the white ball with j written on it.

For every pair of integers (i,j) such that 1 ≤ i < j ≤ N, the black ball with i written on it is to the left of the black ball with j written on it.

In order to achieve this, he can perform the following operation:

Swap two adjacent balls.

Find the minimum number of operations required to achieve the objective.

Constraints

1 ≤ N ≤ 2000

1 ≤ a_i ≤ N

c_i = W or c_i = B.

If i ≠ j, (a_i,c_i) ≠ (a_j,c_j).

Input

Input is given from Standard Input in the following format:

N
c_1 a_1
c_2 a_2
:
c_{2N} a_{2N}

Output

Print the minimum number of operations required to achieve the objective.

Sample Input 1

3
B 1
W 2
B 3
W 1
W 3
B 2

Sample Output 1

4

The objective can be achieved in four operations, for example, as follows:

Swap the black 3 and white 1.

Swap the white 1 and white 2.

Swap the black 3 and white 3.

Swap the black 3 and black 2.

Sample Input 2

4
B 4
W 4
B 3
W 3
B 2
W 2
B 1
W 1

Sample Output 2

18

Sample Input 3

9
W 3
B 1
B 4
W 1
B 5
W 9
W 2
B 6
W 5
B 3
W 8
B 9
W 7
B 2
B 8
W 4
W 6
B 7

Sample Output 3

41



Sample input:
3
B 1
W 2
B 3
W 1
W 3
B 2


Sample output:
4

Submission status: Accepted

Solution code:

"""

普通なら転倒数を計算すればよい
でも今回は…？

最終形を確定すればその転倒数を求めればよくなる
何処に白でどこに黒が良いのかを考える…？

2000 C 2 = 2*(10**6) 通り調べるか…？
1回で2000log2000かかるので無理

転倒数をdpする…？
黒の数を保持してdp → 4000 * 4000 log 4000

戻す場合も転倒数は同じ！！→最重要

まずlistに各色・番の初期位置を記録
BWを決めた時にその位置の数字は確定
その並び替えから元に戻す場合の転倒数を計算！！

O(N^2)で解ける！！
dp[i][j] = 左詰めでBをi個,Ｗをj個置いた時の移動回数の最小値
何回動かす必要があるのか？？



"""

#bit解 O(N^2 * logN)なのできつい

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

"""
def cop(l):

    ret = []
    for i in l:
        ret.append(i)

    return ret


N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(N*2):

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i+1
    else:
        Wlis[a] = i+1

#print (Blis)
#print (Wlis)

#各Bの数での最小の転倒数をBITと別リストで管理

BITs = [[0] * (2*N+1)]
revs = [float("inf")] * (N+1)
revs[0] = 0

#リストが大きすぎて毎回生成はあかん？→Bが大きい方から更新してけばおｋ
#必ず移行しなくてはいけない、具体的な転倒数のリストだけinfで初期化しておけばいい
#回が同じときのjでのBITの中味は固定→copyする必要なし…？

#BITにあらかじめBを置いておく
for i in range(N):

    new = cop(BITs[-1])
    bitadd (Blis[i+1] , 1 , new)
    BITs.append(new)


for i in range(2 * N):

    i += 1

    #BITの更新
    # ～i まで Wの処理をする

    for j in range(min(i , N + 1)):

        if i - j <= N:
            bitadd( Wlis[i-j] , 1 , BITs[j] )

    nrevs = [float("inf")] * (N+1)

    for j in range(min(i , N+1)):

        if i - j <= N:
            nrevs[j] = min(nrevs[j] , revs[j] + ( i - bitsum( Wlis[i-j] , BITs[j])))

        if j != N:
            nrevs[j+1] = min(nrevs[j+1] , revs[j] + (i - bitsum( Blis[j+1] , BITs[j+1] )))

    revs = nrevs
print (revs[-1])

"""

#準備N**2 & dp N**2 解
#WX に関して、まずそれより小さいWxが前にいくつあるかを計算→普通に転倒数
#その後、By(0~N)まで見てWXより前にあるものがいくつかをそれぞれ計算していく
#それをWB逆転に関しても行う→全体でO(N**2)

N = int(input())

Blis = [None] * (N+1)
Wlis = [None] * (N+1)

for i in range(2*N):

    i += 1

    c,a = input().split()
    a = int(a)

    if c == "B":
        Blis[a] = i
    else:
        Wlis[a] = i

#WX,BXそれぞれに関して転倒してない数計算？

B_bef_B = [0] #それ以前にあるそれより小さいBの数
BBIT = [0] * (2 * N + 1)

for i in range(N):
    i += 1

    B_bef_B.append (bitsum(Blis[i] , BBIT))
    bitadd (Blis[i] , 1 , BBIT)

W_bef_W = [0]
WBIT = [0] * (2*N+1)

for i in range(N):
    i += 1
    W_bef_W.append ( bitsum(Wlis[i],WBIT) )
    bitadd (Wlis[i] , 1 , WBIT)

#print (B_bef_B)
#print (W_bef_W)


#次に各BXに関して, WYまで印をつけた時にBXより前にいくつあるかを計算する
#O(N**2)

WY_bef_BX = [[0] * (N+1)] #[x][y]でその数を表示

for x in range(N):
    x += 1

    lis = [0]

    for y in range(N):
        y += 1
        if Wlis[y] < Blis[x]:
            lis.append(lis[-1] + 1)
        else:
            lis.append(lis[-1])

    WY_bef_BX.append(lis)


BY_bef_WX = [[0] * (N+1)]

for x in range(N):
    x += 1

    lis = [0]

    for y in range(N):
        y += 1
        if Blis[y] < Wlis[x]:
            lis.append(lis[-1] + 1)
        else:
            lis.append(lis[-1])

    BY_bef_WX.append(lis)

#print (WY_bef_BX)
#print (BY_bef_WX)

#具体的なDP
#dp[b][w] = b,w番目まで左に寄せた時のコストの最小値
#dp[b][w] = min(dp[b-1][w] + bを足した時のコスト , dp[b][w-1] + wを足した時のコスト)
# bを足した時のコスト = (Blis[b] - 1) - (B_bef_B[b] +  WY_bef_BX[b][w])
# w～　も同じように

dp = [ [float("inf")] * (N+1) for i in range(N+1) ]
dp[0][0] = 0

for i in range(2*N): #iは今現在置いてあるボールの数

    for b in range(i+1):

        w = i-b

        if b < N and w <= N:
            dp[b+1][w] = min(dp[b+1][w] , dp[b][w] + (Blis[b+1] - 1) - (B_bef_B[b+1] + WY_bef_BX[b+1][w]))

        if w < N and b <= N:
            #if b == 2 and w == 0:
                #print (dp[b][w] , (Wlis[w+1] - 1) , W_bef_W[w+1] , BY_bef_WX[b][w+1])
            
            dp[b][w+1] = min(dp[b][w+1] , dp[b][w] + (Wlis[w+1] - 1) - (W_bef_W[w+1] + BY_bef_WX[w+1][b]))

#print (dp)
print (dp[-1][-1])

Submission status: Accepted

Solution code:
from bisect import bisect_right, bisect_left
# instead of AVLTree
class BITbisect():
    def __init__(self, InputProbNumbers):
        # 座圧
        self.ind_to_co = [-10**18]
        self.co_to_ind = {}
        for ind, num in enumerate(sorted(list(set(InputProbNumbers)))):
            self.ind_to_co.append(num)
            self.co_to_ind[num] = ind+1
        self.max = len(self.co_to_ind)
        self.data = [0]*(self.max+1)
    
    def __str__(self):
        retList = []
        for i in range(1, self.max+1):
            x = self.ind_to_co[i]
            if self.count(x):
                c = self.count(x)
                for _ in range(c):
                    retList.append(x)
        return "[" + ", ".join([str(a) for a in retList]) + "]"
    
    def __getitem__(self, key):
        key += 1
        s = 0
        ind = 0
        l = self.max.bit_length()
        for i in reversed(range(l)):
            if ind + (1<<i) <= self.max:
                if s + self.data[ind+(1<<i)] < key:
                    s += self.data[ind+(1<<i)]
                    ind += (1<<i)
        if ind == self.max or key < 0:
            raise IndexError("BIT index out of range")
        return self.ind_to_co[ind+1]
    
    def __len__(self):
        return self._query_sum(self.max)
    
    def __contains__(self, num):
        if not num in self.co_to_ind:
            return False
        return self.count(num) > 0
    
    # 0からiまでの区間和
    # 左に進んでいく
    def _query_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    # i番目の要素にxを足す
    # 上に登っていく
    def _add(self, i, x):
        while i <= self.max:
            self.data[i] += x
            i += i & -i
    
    # 値xを挿入
    def push(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The pushing number didnt initialized")
        self._add(self.co_to_ind[x], 1)
            
    # 値xを削除
    def delete(self, x):
        if not x in self.co_to_ind:
            raise KeyError("The deleting number didnt initialized")
        if self.count(x) <= 0:
            raise ValueError("The deleting number doesnt exist")
        self._add(self.co_to_ind[x], -1)

    # 要素xの個数
    def count(self, x):
        return self._query_sum(self.co_to_ind[x]) - self._query_sum(self.co_to_ind[x]-1)
    
    # 値xを超える最低ind
    def bisect_right(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_right(self.ind_to_co, x) - 1
        return self._query_sum(i)

    # 値xを下回る最低ind
    def bisect_left(self, x):
        if x in self.co_to_ind:
            i = self.co_to_ind[x]
        else:
            i = bisect_left(self.ind_to_co, x)
        if i == 1:
            return 0
        return self._query_sum(i-1)

import sys
input = sys.stdin.readline
INF = 10**14

N = int(input())
white = [None]*N
blue = [None]*N
for i in range(2*N):
    c, n = map(str, input().rstrip().split())
    if c == "W":
        white[int(n)-1] = i
    else:
        blue[int(n)-1] = i

dp1 = [[0]*(N+1) for _ in range(N+1)]
Indb = BITbisect(list(range(2*N+1)))
for j in reversed(range(N)):
    dp1[N][j] = Indb.bisect_left(blue[j])
    Indb.push(blue[j])
    for i in reversed(range(N)):
        if white[i] < blue[j]:
            dp1[i][j] = dp1[i+1][j] + 1
        else:
            dp1[i][j] = dp1[i+1][j]

dp2 = [[0]*(N+1) for _ in range(N+1)]
Indw = BITbisect(list(range(2*N+1)))
for j in reversed(range(N)):
    dp2[j][N] = Indw.bisect_left(white[j])
    Indw.push(white[j])
    for i in reversed(range(N)):
        if blue[i] < white[j]:
            dp2[j][i] = dp2[j][i+1] + 1
        else:
            dp2[j][i] = dp2[j][i+1]

dp = [[INF]*(N+1) for _ in range(N+1)]
dp[N][N] = 0
for i in reversed(range(N+1)):
    for j in reversed(range(N+1)):
        if i == N:
            if j != N:
                dp[i][j] = dp[i][j+1] + dp1[i][j]
        elif j == N:
            dp[i][j] = dp[i+1][j] + dp2[i][j]
        else:
            dp[i][j] = min(dp[i][j+1]+dp1[i][j], dp[i+1][j]+dp2[i][j])
        
print(dp[0][0])

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    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


    N = int(input())
    A = [0] * (2*N)
    idx_W = [0] * (N+1)
    idx_B = [0] * (N+1)
    for i in range(N*2):
        c, a = input().split()
        if c == 'B':
            A[i] = int(a)
            idx_B[A[i]] = i+1
        else:
            A[i] = -int(a)
            idx_W[-A[i]] = i + 1

    cost_W = [[0] * (N+2) for _ in range(N+1)]
    cost_B = [[0] * (N+2) for _ in range(N+1)]
    cost_W_imos = [0] * (N+1)
    cost_B_imos = [0] * (N+1)
    for i in range(2*N):
        if A[i] > 0:
            Ai = A[i]
            cost_W_imos[Ai] = 1
            for j in range(N, 0, -1):
                if j == N:
                    cost_B[Ai][j] = cost_B_imos[j]
                else:
                    cost_B[Ai][j] = cost_B[Ai][j+1] + cost_B_imos[j]
        else:
            Ai = -A[i]
            cost_B_imos[Ai] = 1
            for j in range(N, 0, -1):
                if j == N:
                    cost_W[Ai][j] = cost_W_imos[j]
                else:
                    cost_W[Ai][j] = cost_W[Ai][j + 1] + cost_W_imos[j]

    inv_W = [0] * (N+1)
    inv_B = [0] * (N+1)
    bit_W = Bit(2*N+1)
    bit_B = Bit(2*N+1)
    for i in range(N, 0, -1):
        inv_W[i] = bit_W.sum(idx_W[i])
        inv_B[i] = bit_B.sum(idx_B[i])
        bit_W.add(idx_W[i], 1)
        bit_B.add(idx_B[i], 1)

    inf = (N*2)**2
    dp = [[inf] * (N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N+1):
        for j in range(N+1):
            if i+1 <= N:
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost_W[i+1][j+1] + inv_W[i+1])
            if j+1 <= N:
                dp[i][j+1] = min(dp[i][j+1], dp[i][j] + cost_B[j + 1][i + 1] + inv_B[j + 1])
    print(dp[N][N])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
readline = sys.stdin.readline

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(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
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

N = int(readline())
W = [0]*N
B = [0]*N
for i in range(1, 2*N+1):
    c, a = readline().split()
    if c == 'W':
        W[int(a)-1] = i
    else:
        B[int(a)-1] = i

cw = [0]*(N+1)
cb = [0]*(N+1)
T = BIT(2*N)
for i in range(N):
    cw[i+1] = i-T.get(W[i])
    T.add(W[i], 1)
T = BIT(2*N)
for i in range(N):
    cb[i+1] = i-T.get(B[i])
    T.add(B[i], 1)

invw = [None] + [[0] + list(accumulate([1 if W[i] < B[j] else 0 for j in range(N)])) for i in range(N)]
invb = [None] + [[0] + list(accumulate([1 if B[i] < W[j] else 0 for j in range(N)])) for i in range(N)]
    
inf = 10**9+7
dp = [[inf]*(N+1) for _ in range(N+1)]
dp[0][0] = 0
for s in range(2*N):
    for w in range(max(0, s-N), min(N+1, s+1)):
        b = s-w
        if w != N:
            dp[w+1][b] = min(dp[w+1][b], dp[w][b] + invw[w+1][b] + cw[w+1])
        if b != N:
            dp[w][b+1] = min(dp[w][b+1], dp[w][b] + invb[b+1][w] + cb[b+1])
print(dp[N][N])

Submission status: Accepted

Solution code:
from itertools import accumulate

n = int(input())
b = []
# iがあるインデックス
bc = {}
wc = {}
for i in range(2*n):
    c,a = input().split()
    a = int(a)
    b.append((c,a))
    if c == "B":
        bc[a]=i
    else:
        wc[a]=i

# black[i][j] : 黒のi(1-indexed)のある位置より左にある、i未満の個数 + 白のj以下の個数
black = [[0]*(n+1) for i in range(n+1)]
white = [[0]*(n+1) for i in range(n+1)]

for i in range(2*n):
    c,a = b[i]
    # 同色でa未満の個数 cnt
    cnt = 0
    num = [0]*(n+1)
    for j in range(i):
        if b[j][0] == c:
            if b[j][1] < a:
                cnt += 1
        else:
            num[b[j][1]] += 1
    # 累積和
    num = list(accumulate(num))
    if c == "B":
        black[a] = [j+cnt for j in num]
    else:
        white[a] = [j+cnt for j in num]

DP = [[float("inf")]*(n+1) for i in range(n+1)]
DP[0][0] = 0
for i in range(n+1):
    for j in range(n+1):
        # 黒がi個、白がj個→i+1, j or i, j+1
        if i+1 <= n:
            DP[i+1][j] = min(DP[i+1][j], DP[i][j]+bc[i+1]-black[i+1][j])
        if j+1 <= n:
            DP[i][j+1] = min(DP[i][j+1], DP[i][j]+wc[j+1]-white[j+1][i])
print(DP[n][n])

Submission status: Accepted

Solution code:
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def Add(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
s = [input().split() for _ in range(2*n)]
costb = [[0 for _ in range(n+1)] for _ in range(n+1)]
costw = [[0 for _ in range(n+1)] for _ in range(n+1)]
bitb, bitw = BIT(n), BIT(n)
for i in range(2*n-1, -1, -1):
	c, x = s[i][0], int(s[i][1])
	if c == "B":
		base = bitb.Sum(x-1)
		for j in range(n+1):
			costb[x-1][j] = base + bitw.Sum(j)
		bitb.Add(x, 1)
	else:
		base = bitw.Sum(x-1)
		for j in range(n+1):
			costw[j][x-1] = base + bitb.Sum(j)
		bitw.Add(x, 1)

dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
	for j in range(n+1):
		if i+j == 0:
			continue
		if i == 0:
			dp[i][j] = dp[i][j-1] + costw[i][j-1]
		elif j == 0:
			dp[i][j] = dp[i-1][j] + costb[i-1][j]
		else:
			dp[i][j] = min(dp[i][j-1] + costw[i][j-1], dp[i-1][j] + costb[i-1][j])

print(dp[n][n])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import itertools

N = int(input())

# 各index i と n に対して、左側にn以下のblack/whiteがいくつあるかを数える
# とりあえず1を入れて、あとでcumsum

B_pos = [0] * (N+1)
W_pos = [0] * (N+1)
B_cnt = [[0] * (N+1) for _ in range(2*N)]
W_cnt = [[0] * (N+1) for _ in range(2*N)]

for i in range(2*N):
    c,a = input().split()
    a = int(a) # 0-index化
    if c == 'B':
        B_pos[a] = i
    else:
        W_pos[a] = i
for i in range(1,N+1):
    B_cnt[B_pos[i]][i] += 1
    W_cnt[W_pos[i]][i] += 1
# cumsum
for i in range(1,2*N):
    for j in range(N+1):
        B_cnt[i][j] += B_cnt[i-1][j]
        W_cnt[i][j] += W_cnt[i-1][j]
for i in range(2*N):
    for j in range(1,N+1):
        B_cnt[i][j] += B_cnt[i][j-1]
        W_cnt[i][j] += W_cnt[i][j-1]

B_cnt

W_cnt

# Bi,Wj まで並べるためのコスト
dp = [[0] * (N+1) for _ in range(N+1)]

INF = 1 << 50
for b in range(N+1):
    rng_w = range(N+1) if b else range(1,N+1)
    for w in rng_w:
        p = B_pos[b]
        q = W_pos[w]
        x1,x2 = INF,INF
        if b >= 1:
            x1 = dp[b-1][w] + (p - B_cnt[p][b-1] - W_cnt[p][w])
        if w >= 1:
            x2 = dp[b][w-1] + (q - W_cnt[q][w-1] - B_cnt[q][b])
        dp[b][w] = x1 if x1 < x2 else x2

answer = dp[N][N]
print(answer)

Submission status: Accepted

Solution code:
N=int(input())
Ball=[]
for i in range(2*N):
  c,a=input().split()
  Ball.append((c,int(a)))
B=[0]*N
W=[0]*N
B_table=[[0]*(N+1) for i in range(N)]
W_table=[[0]*(N+1) for i in range(N)]
for i in range(2*N):
  c=Ball[i][1]-1
  if Ball[i][0]=="B":
    B[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="B":
        if Ball[j][1]<Ball[i][1]:
          B_table[Ball[i][1]-1][0]+=1
      elif Ball[j][0]=="W":
        B_table[c][Ball[j][1]]+=1
    for k in range(N):
      B_table[c][k+1]+=B_table[c][k]
  elif Ball[i][0]=="W":
    W[c]=i+1
    for j in range(i+1,2*N):
      if Ball[j][0]=="W":
        if Ball[j][1]<Ball[i][1]:
          W_table[c][0]+=1
      elif Ball[j][0]=="B":
        W_table[c][Ball[j][1]]+=1
    for k in range(N):
      W_table[c][k+1]+=W_table[c][k]
dp=[[0]*(N+1) for i in range(N+1)]
for s in range(1,2*N+1):
  for b in range(max(0,s-N),min(s,N)+1):
    if b==0:
      dp[0][s]=dp[0][s-1]+(W[s-1]+W_table[s-1][0]-s)
    elif b==s:
      dp[s][0]=dp[s-1][0]+(B[s-1]+B_table[s-1][0]-s)
    else:
      dp[b][s-b]=min(dp[b-1][s-b]+(B[b-1]+B_table[b-1][s-b]-s),dp[b][s-b-1]+(W[s-b-1]+W_table[s-b-1][b]-s))
print(dp[N][N])

Submission status: Accepted

Solution code:
# copy
# https://beta.atcoder.jp/contests/arc097/submissions/2509168

N = int(input())
balls = []
for _ in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]

# numB[i][b]: 初期状態において、i番目の玉より右にある、1～bが書かれた黒玉の数
numB = [[0] * (N + 1) for _ in range(2 * N)]
numW = [[0] * (N + 1) for _ in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = list(numB[i])
    numW[i - 1] = list(numW[i])
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1

# costB[b][w]: 黒玉1～b、白玉1～wのうち、初期状態において、黒玉[b+1]より右にある玉の数
costB = [[0] * (N + 1) for _ in range(N + 1)]
costW = [[0] * (N + 1) for _ in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

INF = 10 ** 9 + 7
# dp[b][w]: 黒玉1-b, 白玉1-wまで置いたときの転倒数の最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

print(dp[N][N])

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        n2 = n * 2
        acc = [[0] * n2]
        row = [0] * n2
        for x in rev_c:
            row[n2 - x - 1] += 1
            acc.append(list(reversed(list(accumulate(row)))))
        return acc

    # How many white/black ball lower than 'k' righter than index x? (0<=x<=2N-1)
    # cost[color][k][x]
    cost_w, cost_b = list(map(existence_right, rev))

    dp = [0] + list(accumulate(c[y] for y, c in zip(rev[1], cost_b)))
    for w, x in enumerate(rev[0]):
        ndp = [0] * (n + 1)
        cwx = cost_w[w][x]
        ndp[0] = prev = dp[0] + cwx
        for b, y in enumerate(rev[1]):
            ndp[b + 1] = prev = min(dp[b + 1] + cwx + cost_b[b + 1][x],
                                    prev + cost_w[w + 1][y] + cost_b[b][y])
        dp = ndp
    return dp[n]


n = int(input())
# White/Black 'k' ball is what-th in whole row?
rev = [[0] * n, [0] * n]
for i in range(n * 2):
    c, a = input().split()
    a = int(a) - 1
    rev[int(c == 'B')][a] = i
print(solve(n, rev))

Submission status: Accepted

Solution code:
N = int(input())
balls = []
for i in range(2 * N):
    c, a = input().split()
    balls += [(c, int(a))]

# numB[i][b]: 初期状態において、i番目の玉より右にある、1～bが書かれた黒玉の数
numB = [[0] * (N + 1) for i in range(2 * N)]
numW = [[0] * (N + 1) for i in range(2 * N)]
for i in reversed(range(1, 2 * N)):
    c, a = balls[i]
    numB[i - 1] = list(numB[i])
    numW[i - 1] = list(numW[i])
    if c == 'B':
        for b in range(a, N + 1):
            numB[i - 1][b] += 1
    else:
        for w in range(a, N + 1):
            numW[i - 1][w] += 1

# costB[b][w]: 黒玉1～b、白玉1～wのうち、初期状態において、黒玉[b+1]より右にある玉の数
costB = [[0] * (N + 1) for i in range(N + 1)]
costW = [[0] * (N + 1) for i in range(N + 1)]
for i in reversed(range(2 * N)):
    c, a = balls[i]
    if c == 'B':
        cost = numB[i][a - 1]
        for w in range(N + 1):
            costB[a - 1][w] = cost + numW[i][w]
    else:
        cost = numW[i][a - 1]
        for b in range(N + 1):
            costW[b][a - 1] = cost + numB[i][b]

dp = [[float('inf')] * (N + 1) for i in range(N + 1)]
dp[0][0] = 0
for b in range(N + 1):
    for w in range(N + 1):
        if b > 0:
            dp[b][w] = min(dp[b][w], dp[b - 1][w] + costB[b - 1][w])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w - 1] + costW[b][w - 1])

print(dp[N][N])

Submission status: Accepted

Solution code:
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    c = "BW".index(c); a = int(a)
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N):
    dp[i+1][0] = dp[i][0] + P[i][0]
for i in range(N):
    dp[0][i+1] = dp[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dp[i+1][j+1] = min(dp[i][j+1] + P[i][j+1], dp[i+1][j] + Q[j][i+1])
print(dp[N][N])

Submission status: Accepted

Solution code:
from bisect import bisect
N = int(input())
B = []
BW = []; BB = []
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    c = "BW".index(c)
    B.append((c, a))
    if c:
        MW[a-1] = i
    else:
        MB[a-1] = i

P = [[0]*(N+1) for i in range(N+1)]
Q = [[0]*(N+1) for i in range(N+1)]

for p in range(N):
    cnt = MW[p] - sum(MW[p0] < MW[p] for p0 in range(p))

    P[p][0] = cnt
    for q in range(N):
        if MB[q] < MW[p]:
            cnt -= 1
        P[p][q+1] = cnt

for q in range(N):
    cnt = MB[q] - sum(MB[q0] < MB[q] for q0 in range(q))

    Q[q][0] = cnt
    for p in range(N):
        if MW[p] < MB[q]:
            cnt -= 1
        Q[q][p+1] = cnt

dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
for i in range(N):
    dist[i+1][0] = dist[i][0] + P[i][0]
for i in range(N):
    dist[0][i+1] = dist[0][i] + Q[i][0]
for i in range(N):
    for j in range(N):
        dist[i+1][j+1] = min(dist[i][j+1] + P[i][j+1], dist[i+1][j] + Q[j][i+1])
print(dist[N][N])

Submission status: Runtime Error

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dcw = {}
dcb = {}
for i in range(2*n):
  if ca[i][0] == "W":
    dcw[int(ca[i][2])] = i+1
  else:
    dcb[int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  if i:
    bit0.add(dcw[i],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+dcw[i+1]-bit0.sum(dcw[i+1])-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    if j < n:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dcb[j+1]-bitc.sum(dcb[j+1])-1)
    if i < n:
      dp[i+1][j] = dp[i][j]+dcw[i+1]-bitc.sum(dcw[i+1])-1
    if j < n:
      bitc.add(dcb[j+1],1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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
import sys
input = sys.stdin.readline
from copy import deepcopy
n = int(input())
ca = [input().rstrip() for i in range(2*n)]
dcw = {}
dcb = {}
for i in range(2*n):
  if ca[i][0] == "W":
    dcw[int(ca[i][2])] = i+1
  else:
    dcb[int(ca[i][2])] = i+1
dp = [[10**7 for i in range(n+1)] for j in range(n+1)]
dp[0][0] = 0
bit0 = Bit(2*n)
for i in range(n+1):
  if i:
    bit0.add(dcw[i],1)
  if i < n:
    dp[i+1][0] = dp[i][0]+dcw[i+1]-bit0.sum(dcw[i+1])-1
  bitc = deepcopy(bit0)
  for j in range(n+1):
    if j < n:
      dp[i][j+1] = min(dp[i][j+1],dp[i][j]+dcb[j+1]-bitc.sum(dcb[j+1])-1)
    if i < n:
      dp[i+1][j] = min(dp[i+1][j],dp[i][j]+dcw[i+1]-bitc.sum(dcw[i+1])-1)
    if j < n:
      bitc.add(dcb[j+1],1)
      #print(i,j,dc[bx],bitc.sum(dc[bx]))
print(dp[-1][-1])

Submission status: Runtime Error

Solution code:
class BIT():
    def __init__(self, size):
        self.table = [0 for _ in range(size + 2)]
        self.size = size 
    def Sum(self, i):
        s = 0
        while i>0:
            s+= self.table[i]
            i-=(i&-i)
        return s 

    def Add(self,i,x):
        while i<= self.size:
            self.table[i]+=x 
            i+=(i&-i) 
        return

n=int(input())
s=[input().split() for _ in range(2*n)]
costb = [[0 for _ in range(n+1)] for _ in range(n+1)]
costw = [[0 for _ in range(n+1)] for _ in range(n+1)]
bitb, bitw = BIT(n), BIT(n)
for i in range(2*n-1,-1,-1):
    c,x=s[i][0], int(s[i][1])
    if c=="B":
        base=bitb.Sum(x-1)
        for j in range(n+1):
            costb[x-1][j]= base+bitw.Sum(j)
        bitb.Add(x,1)
    else:
        base=bitw.Sum(x-1)
        for j in range(n+1):
            cost[j][x-1]=base+bitb.Sum(j)
        bitw.Add(x,1)

dp=[[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    for j in range(n+1):
        if i+j==0:
            continue
        if i==0:
            dp[i][j]=dp[i][j-1]+costw[i][j-1]
        elif j==0:
            dp[i][j]=dp[i-1][j]+costb[i-1][j]
        else:
            dp[i][j]=min(dp[i][j-1]+costw[i][j-1], dp[i-1][j]+costb[i-1][j])

print(dp[n][n])

Submission status: Runtime Error

Solution code:
import sys, time
def input():
	return sys.stdin.readline()[:-1]

n = int(input())
a = [list(map(int, input().split()))[::-1] for _ in range(n)]
#print(*a, sep="\n")
opponent = [-1 for _ in range(n)]
match = 0
day = 0
start_time = time.time()
while match < n*(n-1)//2:
	approved = False
	for i in range(n):
		if a[i] != [] and opponent[i] == -1:
			opponent[i] = a[i].pop()-1
	#print(opponent)
	for i in range(n):
		if opponent[i] != -1 and opponent[opponent[i]] == i:
			approved = True
			match += 1
			opponent[opponent[i]] = -1
			opponent[i] = -1
	#print(opponent)
	if not approved:
		print(-1)
		sys.exit()
	now = time.time()
	#print(start_time, now, now - start_time)
	if now-start_time > 1.6:
		print(n*(n-1)//2)
		sys.exit()
	day += 1
print(day)

Submission status: Runtime Error

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

before = {}
n = ni()
INF = 10**18

initial = []
for _ in range(2*n):
    ci, ai = ls()
    ai = int(ai)
    initial.append(ai if ci == "B" else n+ai)
    
lefts = set()
for ii in initial:
    before.update({ii: lefts.copy()})
    lefts.add(ii)
    
dp = [[INF]*(n+1) for _ in range(n+1)]
dp[0][0] = 0

blsets = [[set()]*(n+1) for _ in range(n+1)]

blacks = [set() for _ in range(n+1)]
whites = [set() for _ in range(n+1)]

black = set()
white = set()

for i in range(1,n+1):
    black.add(i)
    white.add(n+i)
    blacks[i] = black.copy()
    whites[i] = white.copy()

for i in range(n+1):
    for j in range(n+1):
        blsets[i][j] = blacks[i] | whites[j]

print(blsets[3][5])

for j in range(1,n+1):
    dp[0][j] = dp[0][j-1] + len(before[n+j]) - len(before[n+j] & blsets[0][j-1])

for i in range(1,n+1):
    dp[i][0] = dp[i-1][0] + len(before[i]) - len(before[i] & blsets[i-1][0])

for i in range(1, n+1):
    for j in range(1, n+1):
        dp[i][j] = min(dp[i-1][j] + len(before[i]) - len(before[i] & blsets[i-1][j]),
                       dp[i][j-1] + len(before[n+j]) - len(before[n+j] & blsets[i][j-1]))
        
print(dp[n][n])

Submission status: Runtime Error

Solution code:
a=2*int(input())
p=[]
t=[]
for i in range(a):
    c=list(raw_input().split(" "))
    t.append((c[0],int(c[1])))
    
def f(t):
    for i in range(0,a-1):
        for j in range(i+1,a):
            if t[i][0]==t[j][0] and t[i][1]>t[j][1]:
                t[j],t[j-1]=t[j-1],t[j]
                p.append(1)
                f(t)
        
            
            
f(t)
print len(p)

Submission status: Runtime Error

Solution code:
a=2*int(input())
p=[]
t=[]
for i in range(a):
    c=list(raw_input().split(" "))
    t.append((c[0],int(c[1])))
    
def f(t):
    for i in range(0,a-1):
        for j in range(i+1,a):
            if t[i][0]==t[j][0] and t[i][1]>t[j][1]:
                t[j],t[j-1]=t[j-1],t[j]
                p.append(1)
                print t
                f(t)
        
            
            
f(t)
print len(p)

Submission status: Runtime Error

Solution code:
a=2*int(input())
p=[]
t=[]
for i in range(a):
    c=list(raw_input().split(" "))
    t.append((c[0],int(c[1])))
    
def f(t):
    for i in range(0,a-1):
        for j in range(i+1,a):
            if (t[i][0]==t[j][0] and t[i][1]>t[j][1]):
                t[j],t[j-1]=t[j-1],t[j]
                p.append(1)
                f(t)
            
f(t)
print len(p)