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: Time Limit Exceeded

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 = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for x, dp0, dp1, c0 in zip(rev[0], dp, dp[1:], cost[0]):
        dp1[0] = dp0[0] + c0[x]
    dp0 = dp[0]
    for b, (y, dp0b, c1) in enumerate(zip(rev[1], dp0, cost[1])):
        dp0[b + 1] = dp0b + c1[y]
    for x, dp0, dp1, cw0, cw1 in zip(rev[0], dp, dp[1:], cost[0], cost[0][1:]):
        cw0x = cw0[x]
        for b, (y, dp01, dp10, cb0, cb1) in enumerate(zip(rev[1], dp0[1:], dp1, cost[1], cost[1][1:])):
            dp1[b + 1] = min(dp01 + cw0x + cb1[x], dp10 + cw1[y] + cb0[y])
    return dp[n][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: Time Limit Exceeded

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 = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        dpw0, dpw1 = dp[w], dp[w + 1]
        cost_wx, cost_w1 = cost[0][w][x], cost[0][w + 1]
        for b, y in enumerate(rev[1]):
            dpw1[b + 1] = min(dpw0[b + 1] + cost_wx + cost[1][b + 1][x],
                              dpw1[b] + cost_w1[y] + cost[1][b][y])
    return dp[n][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: Time Limit Exceeded

Solution code:
from itertools import accumulate


def solve(n, rev):
    def existence_right(rev_c):
        acc = [[0] * (n * 2)]
        row = [0] * (n * 2)
        for x in rev_c:
            row[n * 2 - 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 = list(map(existence_right, rev))

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for w, x in enumerate(rev[0]):
        dp[w + 1][0] = dp[w][0] + cost[0][w][x]
    for b, y in enumerate(rev[1]):
        dp[0][b + 1] = dp[0][b] + cost[1][b][y]
    for w, x in enumerate(rev[0]):
        for b, y in enumerate(rev[1]):
            dp[w + 1][b + 1] = min(dp[w][b + 1] + cost[0][w][x] + cost[1][b + 1][x],
                                   dp[w + 1][b] + cost[0][w + 1][y] + cost[1][b][y])
    return dp[n][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: Time Limit Exceeded

Solution code:
from itertools import accumulate

N = int(input())
balls = []

# 初期位置を覚えておく
placeB = [0] * N
placeW = [0] * N

# 入力処理 & 初期位置処理
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    balls.append([c, a])
    if c == "B":
        placeB[a-1] = i
    else:
        placeW[a-1] = i


costB = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいB
costW = [[0]*(2*N+1) for i in range(N+1)]  # i番目まででjより大きいW

for i in range(N):
    for j in range(2*N):
        if balls[j][1] > i:
            if balls[j][0] == "B":
                costB[i][j+1] = 1
            else:
                costW[i][j+1] = 1

# 累積和
costB = [list(accumulate(cB)) for cB in costB]
costW = [list(accumulate(cW)) for cW in costW]

# dp
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][placeB[b-1]] + costW[w][placeB[b-1]])
        if w > 0:
            dp[b][w] = min(dp[b][w], dp[b][w-1] + costW[w][placeW[w-1]] + costB[b][placeW[w-1]])

print(dp[N][N])

Submission status: Time Limit Exceeded

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] = numB[i].copy()
    numW[i - 1] = numW[i].copy()
    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: Time Limit Exceeded

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: Time Limit Exceeded

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

from heapq import heappush, heappop
dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
while que:
    cost, i, j = heappop(que)
    if dist[i][j] < cost:
        continue
    if i == j == N:
        print(cost)
        break
    if i < N and cost + P[i][j] < dist[i+1][j]:
        dist[i+1][j] = d = cost + P[i][j]
        heappush(que, (d, i+1, j))
    if j < N and cost + Q[j][i] < dist[i][j+1]:
        dist[i][j+1] = d = cost + Q[j][i]
        heappush(que, (d, i, j+1))

Submission status: Time Limit Exceeded

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

from heapq import heappush, heappop
dist = [[10**9]*(N+1) for i in range(N+1)]
dist[0][0] = 0
que = [(0, 0, 0)]
while que:
    cost, i, j = heappop(que)
    if dist[i][j] < cost:
        continue
    if i == j == N:
        print(cost)
        break
    if i < N and cost + P[i][j] < dist[i+1][j]:
        dist[i+1][j] = d = cost + P[i][j]
        heappush(que, (d, i+1, j))
    if j < N and cost + Q[j][i] < dist[i][j+1]:
        dist[i][j+1] = d = cost + Q[j][i]
        heappush(que, (d, i, j+1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

IW = [MW[a]+1 for a in AW]
IB = [MB[a]+1 for a in AB]

for i in range(1, 2*N+1):
    data[i] = i & -i

for i, p in enumerate(IW):
    cWi = cW[i]; cBi = cB[i]
    for j, q in enumerate(IB):
        cWi[j] = get(p)-1
        cBi[j] = get(q)-1
        add(q, -1)
    cWi[N] = get(p)-1

    for q in IB:
        add(q, 1)
    add(p, -1)
cBi = cB[N]
for j, q in enumerate(IB):
    cBi[j] = get(q)-1
    add(q, -1)

rN1 = range(1, N+1)
dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = tmp = 0
T = dp[0]; cBi = cB[0]
for j in rN1:
    tmp = T[j] = tmp + cBi[j-1]

for i in rN1:
    T = dp[i]
    S = dp[i-1]
    cWi = cW[i-1]; cBi = cB[i]
    tmp = T[0] = S[0] + cWi[0]
    for j in rN1:
        tmp = T[j] = min(S[j] + cWi[j], tmp + cBi[j-1])
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

IW = [MW[a]+1 for a in AW]
IB = [MB[a]+1 for a in AB]

for i in range(2*N):
    add(i+1, 1)
for i in range(N):
    cWi = cW[i]; cBi = cB[i]
    for j in range(N):
        cWi[j] = get(IW[i])-1
        cBi[j] = get(IB[j])-1
        add(IB[j], -1)
    cWi[N] = get(IW[i])-1

    for j in range(N):
        add(IB[j], 1)
    if i < N:
        add(IW[i], -1)
cBi = cB[N]
for j in range(N):
    cBi[j] = get(IB[j])-1
    add(IB[j], -1)

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    T = dp[i]
    S = dp[i-1]
    cWi = cW[i-1]; cBi = cB[i]
    for j in range(N+1):
        v = T[j]
        if i:
            v = min(v, S[j] + cWi[j])
        if j:
            v = min(v, T[j-1] + cBi[j-1])
        T[j] = v
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

IW = [MW[a]+1 for a in AW]
IB = [MB[a]+1 for a in AB]

for i in range(2*N):
    add(i+1, 1)
for i in range(N):
    cWi = cW[i]; cBi = cB[i]
    for j in range(N):
        cWi[j] = get(IW[i])-1
        cBi[j] = get(IB[j])-1
        add(IB[j], -1)
    cWi[N] = get(IW[i])-1

    for j in range(N):
        add(IB[j], 1)
    if i < N:
        add(IW[i], -1)
cBi = cB[N]
for j in range(N):
    cBi[j] = get(IB[j])-1
    add(IB[j], -1)

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    T = dp[i]
    S = dp[i-1]
    cWi = cW[i-1]; cBi = cB[i]
    for j in range(N+1):
        v = T[j]
        if i:
            v = min(v, S[j] + cWi[j])
        if j:
            v = min(v, T[j-1] + cBi[j-1])
        T[j] = v
print(dp[N][N])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
MB = {}; MW = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    #B.append(("BW".index(c), a))
    if c == 'W':
        MW[a] = i
    else:
        MB[a] = i
data = [0]*(2*N+1)
def add(k, x):
    while k <= 2*N:
        data[k] += x
        k += k & -k
def get(k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
AW = sorted(MW)
AB = sorted(MB)
cB = [[0]*(N+1) for i in range(N+1)]
cW = [[0]*(N+1) for i in range(N+1)]

for i in range(2*N):
    add(i+1, 1)
for i in range(N+1):
    for j in range(N+1):
        if i < N:
            cW[i][j] = get(MW[AW[i]]+1)-1
        if j < N:
            cB[i][j] = get(MB[AB[j]]+1)-1
        #print(i, j, cW[i][j], cB[i][j])
        if j < N:
            add(MB[AB[j]]+1, -1)
    for j in range(N):
        add(MB[AB[j]]+1, 1)
    if i < N:
        add(MW[AW[i]]+1, -1)

dp = [[10**9]*(N+1) for i in range(N+1)]
dp[0][0] = 0
for i in range(N+1):
    for j in range(N+1):
        v = dp[i][j]
        if i > 0:
            v = min(v, dp[i-1][j] + cW[i-1][j])
        if j > 0:
            v = min(v, dp[i][j-1] + cB[i][j-1])
        dp[i][j] = v
print(dp[N][N])

Submission status: Accepted

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

N = int(input())
c = [0] * (2 * N)
a = [0] * (2 * N)
for i in range(2 * N):
    c[i], a[i] = input().split()
    a[i] = int(a[i]) - 1

idx = [[0] * 2 for _ in range(N)]
for i in range(2 * N):
    idx[a[i]][c[i] == 'W'] = i

costB = [[0] * (N + 1) for _ in range(N)]
for i in range(N):
    j = idx[i][0]
    cnt = 0
    for k in range(i):
        if j < idx[k][0]:
            cnt += 1
    costB[i][0] = j + cnt - i
    cnt2 = 0
    for k in range(1, N + 1):
        if j < idx[k - 1][1]:
            cnt2 += 1
        costB[i][k] = j + cnt + cnt2 - (i + k)

costW = [[0] * (N + 1) for _ in range(N)]
for i in range(N):
    j = idx[i][1]
    cnt = 0
    for k in range(i):
        if j < idx[k][1]:
            cnt += 1
    costW[i][0] = j + cnt - i
    cnt2 = 0
    for k in range(1, N + 1):
        if j < idx[k - 1][0]:
            cnt2 += 1
        costW[i][k] = j + cnt + cnt2 - (i + k)

dp = [[10**18] * (N + 1) for _ in range(2 * N + 1)]
dp[0][0] = 0
for i in range(1, 2 * N + 1):
    for j in range(max(0, i - N), min(i, N) + 1):
        dp[i][j] = dp[i-1][j] + costW[i-j-1][j]
        if j > 0:
            dp[i][j] = min(dp[i][j], dp[i-1][j-1] + costB[j-1][i-j])
print(dp[2*N][N])

Submission status: Accepted

Solution code:
def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

# 解説AC
def examE():
    N = I()
    Bnum = [-1]*N
    Wnum = [-1]*N
    B = {}
    W = {}
    for i in range(2*N):
        c, a = LSI()
        a = int(a)-1
        if c=="W":
            W[i] = a+1
            Wnum[a] = i
        else:
            B[i] = a+1
            Bnum[a] = i
    SB = [[0]*(N*2) for _ in range(N+1)]; SW = [[0]*(N*2) for _ in range(N+1)]
    for i in range(2*N):
        if not i in B:
            continue
        cur = B[i]
        cnt = 0
        SB[cur][i] = 0
        for j in range(2*N):
            if not j in B:
                SB[cur][j] = cnt
                continue
            if B[j]<=cur:
                cnt += 1
            SB[cur][j] = cnt
    for i in range(2*N):
        if not i in W:
            continue
        cur = W[i]
        cnt = 0
        SW[cur][i] = 0
        for j in range(2*N):
            if not j in W:
                SW[cur][j] = cnt
                continue
            if W[j]<=cur:
                cnt += 1
            SW[cur][j] = cnt
    #for b in SB:
        #print(b)
    #print(SW)
    #print(SW,len(SW))

    dp = [[inf]*(N+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(N):
        dp[0][i+1] = dp[0][i]+Bnum[i]-SB[i][Bnum[i]]
        dp[i+1][0] = dp[i][0]+Wnum[i]-SW[i][Wnum[i]]
    #print(dp)
    for i in range(N):
        w = Wnum[i]
        for j in range(N):
            b = Bnum[j]
            costb = b - (SB[j][b]+SW[i+1][b])
            costw = w - (SB[j+1][w]+SW[i][w])
            #if i==2 and j==4:
            #    print(w,SB[i][w],SW[j+1][w])
            #    print(b,SB[i][b],SW[j+1][b])
            #print(costb,costw,i,j)
            #input()
            if costb<0:
                costb = 0
                #print(i,j)
            if costw < 0:
                costw = 0
                #print(i,j)
            dp[i+1][j+1] = min(dp[i+1][j+1],dp[i+1][j]+costb,dp[i][j+1]+costw)
    ans = dp[-1][-1]
    #for v in dp:
    #    print(v)
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

    n = int(input())
    ab = [list(input().split()) for _ in [0]*(2*n)]
    ab = [(a == "B", int(b)-1) for a, b in ab]
    dct_b = [0]*n
    dct_w = [0]*n
    for i, (a, b) in enumerate(ab):
        if a:
            dct_b[b] = i
        else:
            dct_w[b] = i

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    # 左i個にあるj以上のボールの数
    lb = [[0]*(n+1) for _ in [0]*(2*n)]
    lw = [[0]*(n+1) for _ in [0]*(2*n)]

    for j in range(n):
        cnt1, cnt2 = 0, 0
        for i, (a, b) in enumerate(ab):
            lb[i][j] = cnt1
            lw[i][j] = cnt2
            if a:
                if b >= j:
                    cnt1 += 1
            else:
                if b >= j:
                    cnt2 += 1

    dp = [[10**9]*(n+1) for _ in [0]*(n+1)]  # dp[i][j] = Bをi個、Wをj個置くための最小手数
    dp[0][0] = 0

    for i in range(n+1):
        dp1 = dp[i]
        if i < n:
            dp2 = dp[i+1]
            t = dct_b[i]
        for j in range(n+1):
            d = dp1[j]
            if i < n:
                dp2[j] = min(dp2[j], d+lb[t][i]+lw[t][j])
            if j < n:
                t2 = dct_w[j]
                dp1[j+1] = min(dp1[j+1], d+lb[t2][i]+lw[t2][j])
    print(dp[n][n])


main()

Submission status: Accepted

Solution code:
N=int(input())
dic={"B":[0]*N,"W":[0]*N}
for i in range(2*N):
    c,a=input().split()
    a=int(a)
    dic[c][a-1]=i

Btable=[[0 for i in range(N+1)] for i in range(N)]
BBtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["B"][i]<dic["B"][j])
    BBtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["W"][j-1]>dic["B"][i]:
            S+=1
        Btable[i][j]=S+BBtable[i]
    Btable[i][0]=BBtable[i]

Wtable=[[0 for i in range(N+1)] for i in range(N)]
WWtable=[0 for i in range(N)]
S=0
for i in range(1,N):
    S=0
    for j in range(0,i):
        S+=(dic["W"][i]<dic["W"][j])
    WWtable[i]=S

for i in range(N):
    S=0
    for j in range(1,N+1):
        if dic["B"][j-1]>dic["W"][i]:
            S+=1
        Wtable[i][j]=S+WWtable[i]
    Wtable[i][0]=WWtable[i]

dp=[[0 for j in range(N+1)] for i in range(N+1)]

for j in range(N-1,-1,-1):
    dp[N][j]=dp[N][j+1]+Wtable[j][N]

for i in range(N-1,-1,-1):
    for j in range(N,-1,-1):
        if j!=N:
            dp[i][j]=min(dp[i+1][j]+Btable[i][j],dp[i][j+1]+Wtable[j][i])
        else:
            dp[i][j]=dp[i+1][j]+Btable[i][j]


print(dp[0][0])

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:
import sys
input = sys.stdin.readline


n = int(input())
INF = 10 ** 9
info = [list(input().split()) for i in range(2 * n)]

ind = {}
for i in range(2 * n):
    if info[i][0] == "B":
        info[i] = (0, int(info[i][1]))
    else:
        info[i] = (1, int(info[i][1]))
    ind[info[i][0] * 10 ** 5 + info[i][1]] = i

ru_b = [[0] * (2 * n + 1) for i in range(n + 1)]
ru_w = [[0] * (2 * n + 1) for i in range(n + 1)]
for i in range(n + 1):
    for j in range(2 * n):
        col, num = info[j]
        if col == 0 and num > i:
            ru_b[i][j + 1] += 1
        elif col == 1 and num > i:
            ru_w[i][j + 1] += 1
    for j in range(2 * n):
        ru_b[i][j + 1] += ru_b[i][j]
        ru_w[i][j + 1] += ru_w[i][j]    


dp = [[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):
        if i + 1 <= n and j <= n:
            bi = ind[i + 1]
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + ru_b[i][bi] + ru_w[j][bi])
        if i <= n and j + 1 <= n:
            wi = ind[10 ** 5 + j + 1]
            dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + ru_w[j][wi] + ru_b[i][wi])

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

Submission status: Accepted

Solution code:
N = int(input())
X = [i for i in range(N+1)]
Y = [[] for _ in range(N)]
B, W = [], []
ans = 0
for i in range(2 * N):
    c, a = input().split()
    a = int(a) - 1
    if c == "B":
        X = [X[i] + 1 if i <= a else X[i] - 1 for i in range(N+1)]
        B.append(a)
        ans += len([b for b in B if b > a])
    else:
        Y[a] = X[:]
        W.append(a)
        ans += len([b for b in W if b > a])

Z = [0] * (N+1)
for y in Y:
    for i in range(N+1):
        Z[i] += y[i]
    for i in range(1, N+1):
        Z[i] = min(Z[i], Z[i-1])

ans += Z[-1]
print(ans)

Submission status: Accepted

Solution code:
import itertools
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    """
    cs = 0
    ret = []
    for v in it:
        cs += v
        ret.append(cs)
    return ret


# 解説
N = int(sys.stdin.buffer.readline())
CA = [sys.stdin.buffer.readline().decode().rstrip().split() for _ in range(N * 2)]
C = []
A = []
for c, a in CA:
    C.append(c)
    A.append(int(a))

pos_w = [IINF] * (N + 1)
pos_b = [IINF] * (N + 1)
for i, (c, a) in enumerate(list(zip(C, A))):
    if c == 'W':
        pos_w[a] = i
    else:
        pos_b[a] = i

# count_b[k][i]: i より左に、k 以下の黒が何個あるか
# count_w[k][i]: i より左に、k 以下の白が何個あるか
bc = [0] * (N * 2 + 1)
wc = [0] * (N * 2 + 1)
count_b = [[0] * (N * 2 + 1)]
count_w = [[0] * (N * 2 + 1)]
for k in range(1, N + 1):
    wc[pos_w[k] + 1] = 1
    bc[pos_b[k] + 1] = 1
    count_b.append(cumsum(bc))
    count_w.append(cumsum(wc))

# dp[b][w]: B を b 回、W を w 回使ったときの転倒数の最小値
dp = [[INF] * (N + 1) for _ in range(N + 1)]
dp[0][0] = 0
# for i in range(N * 2):
#     b = i
#     w = 0
#     if b > N:
#         w = b - N
#         b -= w
#
#     while w <= min(i, N):
#         if b < N:
#             # b + 1 を使う。
#             # 位置の写像が与えられたときのスワップの回数だから転倒数
#             # もともといた位置より右にあったやつで、既に使ってるのが何個か
#             orig_pos = pos_b[b + 1]
#             inv = i - count_b[b + 1][orig_pos] - count_w[w][orig_pos]
#             dp[b + 1][w] = min(dp[b + 1][w], dp[b][w] + inv)
#         if w < N:
#             orig_pos = pos_w[w + 1]
#             inv = i - count_b[b][orig_pos] - count_w[w + 1][orig_pos]
#             dp[b][w + 1] = min(dp[b][w + 1], dp[b][w] + inv)
#         b -= 1
#         w += 1


# もらう
for b, w in itertools.product(range(N + 1), repeat=2):
    if b > 0:
        # 最後に b を使う
        orig_pos = pos_b[b]
        inv = b - count_b[b][orig_pos] + w - count_w[w][orig_pos] - 1
        dp[b][w] = min(dp[b][w], dp[b - 1][w] + inv)
    if w > 0:
        # 最後に w を使う
        orig_pos = pos_w[w]
        inv = b - count_b[b][orig_pos] + w - count_w[w][orig_pos] - 1
        dp[b][w] = min(dp[b][w], dp[b][w - 1] + inv)
print(dp[N][N])

# import numpy as np
#
# print(np.array(dp))