kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_6_D: Minimum Cost Sort (続き3)

変数がいっぱいあるから追っかけにくいんだな
といっても単純にmapとかreduceになる形でもなさそう

サイクルに分けるところと計算するところを分けたらどうかな
ちょっとずつCPUとメモリがもったいないけど

def solve(n, A):
    def cycles():
        V = [False] * n
        B = sorted(A)
        T = {B[i]: i for i in range(n)}
        C = []

        for i in range(n):
            if V[i]:
                continue
            cur = i
            cycle = []
            while not V[cur]:
                V[cur] = True
                cycle.append(cur)
                cur = T[A[cur]]
            C.append(cycle)

        return C

    ans = 0
    s = min(A)

    for cycle in cycles():
        S = sum([A[i] for i in cycle])
        m = min([A[i] for i in cycle])
        an = len(cycle)
        ans += min(S + (an - 2) * m, m + S + (an + 1) * s)

    return ans

微妙か
いやでもちょっとはわかりやすくなったんじゃないかな
cyclesの外側はすっきりしたし
cyclesの中はもうちょっとなんとかならないかという気もするけど

00.02s 5720KB が 00.02s 5856KB になっただけなので
処理時間やメモリへの影響は無視