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 になっただけなので
処理時間やメモリへの影響は無視