0 GP
【筆記】學著一步一步將一堆迴圈拆掉
作者:♙♲⚙\~O_O~/⚙♲♙│2021-06-10 05:08:32│巴幣:0│人氣:209
此為閱讀筆記,僅因本人理解力不甚充足而記錄。
閱讀之原文:https://home.gamer.com.tw/creationDetail.php?sn=4910101
題目:https://codeforces.com/contest/1400/problem/D
題目概述
given array A of int of size n>=4
0<=i<j<k<l<n , 0<=a_x<=n
Question: find the number of tuples s.t. a_i == a_k && a_j == a_l
原始作法
for i in range(n):
for j in range(i+1,n):
for k in range(j+1,n):
for l in range(k+1,n):
if A[i]==A[k] and A[j]==A[l]:
ans+=1
以下進行最佳化:
1. 如果建一張表,紀錄某個位置之前各個數字出現過幾次,則不用找i。可以把 for i 拆掉, j 改從0+1=1開始:
# 建表
# (略)
for j in range(1,n):
for k in range(j+1,n):
for l in range(k+1,n):
if A[j]==A[l]:
ans+=table[j][A[k]] # 在j之前A[k]這個數字出現過的次數
2. 注意到最低就是j,在j之前的資料不會再被看過。把表壓成1維:
for j in range(n):
for k in range(j+1,n):
for l in range(k+1,n):
if A[j]==A[l]:
ans+=table[A[k]]
table[A[j]]+=1
3. 條件判斷式跟k好像沒甚麼關聯,試著拆 for k 。先把它拿進深層,讓他與有關聯的東西密切一點:
for j in range(n):
for l in range(j+2,n):
if A[j]==A[l]:
for k in range(j+1,l):
ans+=table[A[k]]
table[A[j]]+=1
4. 讓 sum([table[A[k]] for k in range(j+1,l)]) 先算完再放進ans
for j in range(n):
for l in range(j+2,n):
if A[j]==A[l]:
ans+=sum([table[A[k]] for k in range(j+1,l)])
table[A[j]]+=1
5. k 那段加太多次 j~後面 的東西了,欠prefixsum
for j in range(n):
prefixAtJ=[0]*j+[table[A[j]]]
for jj in range(j+1,n):
prefixAtJ[jj]=prefixAtJ[jj-1]+table[A[jj]]
for l in range(j+2,n):
s+=table[A[l-1]]
if A[j]==A[l]:
ans+=prefixAtJ[l-1]-prefixAtJ[j]
table[A[j]]+=1
6. 迴圈跑兩次不累嗎,更何況不一定會發生 A[j]==A[l] ,壓平
for j in range(n):
s=0
for l in range(j+2,n):
s+=table[A[l-1]]
if A[j]==A[l]:
ans+=s
table[A[j]]+=1
7. for l 那邊攤開後調個順序就跟原文的一樣了
引用網址:https://home.gamer.com.tw/TrackBack.php?sn=5173814
All rights reserved. 版權所有,保留一切權利