創作內容

0 GP

【筆記】學著一步一步將一堆迴圈拆掉

作者:♙♲⚙\~O_O~/⚙♲♙│2021-06-10 05:08:32│巴幣:0│人氣:198
此為閱讀筆記,僅因本人理解力不甚充足而記錄。

閱讀之原文: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. 版權所有,保留一切權利

相關創作

同標籤作品搜尋:演算法

留言共 0 篇留言

我要留言提醒:您尚未登入,請先登入再留言

喜歡★agold404 可決定是否刪除您的留言,請勿發表違反站規文字。

前一篇:【RMMV】plugin... 後一篇:現在看個新聞網頁還要被迫...

追蹤私訊切換新版閱覽

作品資料夾

rogerjian喜歡像素風格的人
歡迎參觀LINE貼圖小舖看更多我要大聲說昨天21:48


face基於日前微軟官方表示 Internet Explorer 不再支援新的網路標準,可能無法使用新的應用程式來呈現網站內容,在瀏覽器支援度及網站安全性的雙重考量下,為了讓巴友們有更好的使用體驗,巴哈姆特即將於 2019年9月2日 停止支援 Internet Explorer 瀏覽器的頁面呈現和功能。
屆時建議您使用下述瀏覽器來瀏覽巴哈姆特:
。Google Chrome(推薦)
。Mozilla Firefox
。Microsoft Edge(Windows10以上的作業系統版本才可使用)

face我們了解您不想看到廣告的心情⋯ 若您願意支持巴哈姆特永續經營,請將 gamer.com.tw 加入廣告阻擋工具的白名單中,謝謝 !【教學】