AtCoder Beginner Contest 296 F,Ex問題メモ

def solve(n, aaa, bbb):
    if sorted(aaa) != sorted(bbb):
        return False

    if len(set(aaa)) < len(aaa):
        return True

    pos = {a: i for i, a in enumerate(aaa)}

    for i in range(n - 2):
        if aaa[i] == bbb[i]:
            continue

        k = pos[bbb[i]]
        if i + 1 == k:
            j = i + 2
        else:
            j = i + 1

        a = aaa[i]
        b = aaa[j]
        c = aaa[k]
        aaa[i] = c
        aaa[j] = a
        aaa[k] = b
        pos[c] = i
        pos[a] = j
        pos[b] = k

    if aaa[-1] == bbb[-1]:
        return True

    else:
        return False


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))

ans = solve(n, aaa, bbb)
print('Yes' if ans else 'No')

from collections import defaultdict


def pop_count_8(n):
    c = (n & 0x55) + ((n >> 1) & 0x55)
    c = (c & 0x33) + ((c >> 2) & 0x33)
    c = (c & 0x0f) + ((c >> 4) & 0x0f)
    return c


transit_memo = {}


def transit(prev_row, prev_mat, curr_row):
    """
    前の行の黒マス・接続状況と、今の行の黒マスから、それが可能な遷移か、可能なら今の行の接続状況がどうなるかを返す。
    状態は限られているため、メモ化することで高速になる
    """
    if (prev_row, prev_mat, curr_row) in transit_memo:
        return transit_memo[prev_row, prev_mat, curr_row]

    curr_mat = 0
    checked = 0
    for s in range(m):
        sb = 1 << s
        if curr_row & sb == 0:
            continue
        if checked & sb:
            continue
        grp = sb
        checked |= sb
        q = [sb]  # 現在の行[0,m) 前の行[m,2m)
        while q:
            ub = q.pop()
            if ub < p2m:

                vb = ub << 1
                if vb != p2m and (curr_row & vb) and (checked & vb == 0):
                    q.append(vb)
                    grp |= vb
                    checked |= vb
                vb = ub >> 1
                if vb != 0 and (curr_row & vb) and (checked & vb == 0):
                    q.append(vb)
                    grp |= vb
                    checked |= vb
                vb = ub << m
                if (prev_row & (vb >> m)) and (checked & vb == 0):
                    q.append(vb)
                    checked |= vb
            else:
                vb = ub >> m
                if (curr_row & vb) and (checked & vb == 0):
                    q.append(vb)
                    grp |= vb
                    checked |= vb
                u = bit2idx[ub >> m]
                for v in range(m):
                    vb = 1 << (v + m)
                    if u != v and (prev_mat & (1 << (u * m + v))) and (checked & vb == 0):
                        q.append(vb)
                        checked |= vb

        for u in range(s, m):
            ub = 1 << u
            if grp & ub == 0:
                continue
            for v in range(u + 1, m):
                vb = 1 << v
                if grp & vb:
                    curr_mat |= 1 << (u * m + v)
                    curr_mat |= 1 << (v * m + u)

    # 前の行から繋がらないマスがある
    if ~(checked >> m) & prev_row:
        res = -1
    else:
        res = curr_mat

    transit_memo[prev_row, prev_mat, curr_row] = res
    return res


n, m = map(int, input().split())
field = []
for _ in range(n):
    s = input()
    field.append(int(s.replace('.', '0').replace('#', '1'), 2))

# 最初行と最終行に必ず黒マスがあるようにする
i = 0
while field[i] == 0:
    i += 1
field = field[i:]
while field[-1] == 0:
    field.pop()

bit2idx = {1 << i: i for i in range(m)}
INF = 1 << 60
dp_factory = lambda: INF

dp = {0: 0}
# dp key: (前のrowに配置した黒マスのbitset << m*m) | (前の行の接続関係を示すm*mのmatrixを1つのbitsetにしたもの)
# dp value: keyの状態にするのに必要な最小追加黒マス数
p2m = 1 << m
p2m2 = 1 << (m * 2)

mm = m * m
mask_mm = (1 << mm) - 1
mask_m = (1 << m) - 1

for orig_row in field:
    ndp = defaultdict(dp_factory)

    # 現在行の白マス集合（黒マスを置ける集合）
    cleared_bits = mask_m & ~orig_row

    for key, count in dp.items():
        prev_row = key >> mm
        prev_mat = key & mask_mm

        set_bits = cleared_bits
        prev_set_bits = -1
        while prev_set_bits != 0:
            curr_row = orig_row | set_bits
            prev_set_bits = set_bits
            set_bits = (set_bits - 1) & cleared_bits

            curr_mat = transit(prev_row, prev_mat, curr_row)

            if curr_mat == -1:
                continue

            new_count = count + pop_count_8(orig_row ^ curr_row)
            new_key = (curr_row << mm) | curr_mat

            ndp[new_key] = min(ndp[new_key], new_count)

    dp = ndp

ans = INF
for key, count in dp.items():
    row = key >> mm
    mat = key & mask_mm
    ib = row & -row
    i = bit2idx[ib]
    # 最終行に配置された黒マスが全て連結状態にあるかチェック
    if (row ^ ib) == ((mat >> (i * m)) & mask_m):
        ans = min(ans, count)

print(ans)