Submission #6362007

---

Source Code Expand

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 Info

Judge Result