406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
往LRU Cache，把跑過的結果存起來，這樣的方向是對的嗎？
我一直Time out...
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
有動態儲存會比較快, 全部存起來不可能, 因為記憶體不夠, 我是把小於某值的結果才存起來。
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
這是我的秒數
#0: 25% AC (0.8s, 15.6MB)
通過檢測
#1: 25% AC (76ms, 14MB)
通過檢測
#2: 25% AC (2s, 19.1MB)
通過檢測
#3: 25% AC (3s, 24.6MB)
通過檢測
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
這是我的秒數
#0: 25% AC (0.8s, 15.6MB)
通過檢測#1: 25% AC (76ms, 14MB)
通過檢測#2: 25% AC (2s, 19.1MB)
通過檢測#3: 25% AC (3s, 24.6MB)
通過檢測
你是使用遞迴的寫法嗎？還是使用迴圈呢？
我是使用遞迴，並且改成限制在n<10000，有50%!
但 #3 #4依然TLE，哈
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
我是遞迴設 1250000
對耶！我忘記 n 其實會超出10的6次方！
最後把範圍設125萬(驚人@@我不敢設這麼大)，然後使用array作為陣列索引就過了！
謝謝你，你真厲害！
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
我把 array改為 list 有快一點。
另外 oeis 有公式可查。
OEIS有公式 :O
我只有找到前10000項，原本想直接套，但是程式碼太大塞不下
https://oeis.org/A006577
list的部分改天來試試
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
你也可以玩奇數才建表，也許更快。
原本有嘗試這種作法
可是表不知道要建多大了，可能沒辦法陣列索引
使用dict應該會塞不下(或是我方法有用錯)
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
奇數除2的值當索引建表，表可以建2倍大。
偶數連除2到奇數，才進遞迴，想像會變快。晚安。
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
1.8s 的 Lanstar 大大，有打算現身說法一下嗎 XD
你使用的方法是什麼呢？分享一下哈
我很少會點進討論區，一進來就看到我的名字 哈
我是用遞迴，陣列只開1000000
原本想說開大一點可以節省時間，但反而更慢了..
奇偶分開做會快很多
奇數：如果>333333，可以直接丟 (x*3+1)//2 進遞迴，次數要再加一
否則，丟 x*3+1 進遞迴
偶數：丟 x//2 進遞迴
建表的時候也是。
因為我是由小到大建表，偶數的部分可以直接取 DP 中 x//2 的值
我也不知道還能不能再更快
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
406490150@gms.tku.edu.tw
(我是朱朱)
學校
:
國立交通大學
編號 : 139794
來源 : [140.113.236.122]
最後登入時間 ：
2022-09-03 11:13:16
我很少會點進討論區，一進來就看到我的名字 哈
我是用遞迴，陣列只開1000000
原本想說開大一點可以節省時間，但反而更慢了..
奇偶分開做會快很多
奇數：如果>333333，可以直接丟 (x*3+1)//2 進遞迴，次數要再加一
否則，丟 x*3+1 進遞迴
偶數：丟 x//2 進遞迴
建表的時候也是。
因為我是由小到大建表，偶數的部分可以直接取 DP 中 x//2 的值
我也不知道還能不能再更快
雖然認為陣列大小也會影響執行結果，但陣列太大反而索引效率差嗎？ :O
真是神奇的觀察