提出 #22746299

---

ソースコード 拡げる

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def from_read(dtype=np.int64):
    return np.fromstring(read().decode(), dtype=dtype, sep=' ')


def from_readline(dtype=np.int64):
    return np.fromstring(readline().decode(), dtype=dtype, sep=' ')

def main(N, A, B):
    INF = 1 << 60
    DP = {(0, 0): np.zeros(N + 1, np.int32)}
    stack = [(0, 1 << N)]
    while stack:
        L, R = stack[-1]
        i = np.searchsorted(A, L, 'right') - 1
        assert A[i] <= L < A[i + 1]
        if R <= A[i + 1]:
            b = B[i]
            stack.pop()
            for k in range(N + 1):
                if R - L == 1 << k:
                    break
            """
            2^k 人の山。いま、全員に b 位が割り当てられている。
            """
            winner = N - k
            dp = np.full(N + 1, INF, np.int32)
            if b < winner:
                # 優勝者がさらに勝ち進んだ場合だけ、コストが下がる
                dp[:] = R - L
                dp[winner - b] -= 1
            elif b > winner:
                # 何をやってもコストは定数
                dp[:] = R - L - (1 << (b - winner - 1))
            else:
                dp[0] = R - L - 1
                dp[1:] = R - L
            # print(L, R, dp)
            DP[L, R] = dp
            continue
        M = (L + R) // 2
        if (L, M) in DP:
            dp_1 = DP[L, M]
            dp_2 = DP[M, R]
            del DP[L, M]
            del DP[M, R]
            stack.pop()

            dp = np.full(N + 1, INF, np.int32)
            for i in range(N):
                dp[i] = min(dp_1[i + 1] + dp_2[0], dp_1[0] + dp_2[i + 1])
            # print(L, R, dp)
            DP[L, R] = dp
            continue
        stack.append((L, M))
        stack.append((M, R))
    return DP[0, 1 << N][0]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba import njit, b1, i4, i8, f8
    from numba.pycc import CC
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8, i8[:], i8[:]))
    cc.compile()

from my_module import main

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

print(main(N, A, B))

提出情報

ジャッジ結果