還好在出那道題目時我有把當初的解法寫成講義，裡面甚至有我親自寫的詳細解題過程跟公式，不過由於已經是好多年前，解法差不多全忘光了，只好一邊看著講義一邊慢慢回想當初是怎麼解的？
就這樣搞了一個多小時，好像把解法弄懂了 ，但這題是個變化型，又得想想要怎麼兜？也許是太早醒來，腦袋還僵僵的，又弄了一個小時才發現要怎樣改，可以用我以前那題寫好的程式，但要改寫某一個部份，這樣又花了幾十分鐘，終於改好了。然後試跑F(25!)跟F(100!)都得到正確數字，然後開始測時間，發覺F(1000!)要1.8秒，F(10000!)約18秒，F(n!)所需的時間跟n成正比。
此時一看已6個人解出來了，好像要拼前十有望了。可是我F(1000000!)要跑超久的，會不會程式跑完都十幾個人解出來了？只好想想看要怎麼改進速度。正在苦思要怎麼改進速度時，又一個人解出來了，變7個人了。不管了，拼看看！直接跑耗時的程式，反正PE又不是真正的程式競賽，沒有TLE的問題也沒有記憶體使用量的限制(程式愛跑多久就跑多久，記憶體愛開多大就開多大)。於是就決定讓機器去跑，跑到一半又覺得某個地方可以改進，把程式按掉，改寫了那個部份，結果速度根本沒改善嘛！還是一樣F(1000!)要1.8秒，F(10000!)約18秒，多此一舉兼浪費時間，不管了，讓機器去跑吧！在跑的時候，心裡超忐忑的，該不會那麼倒霉吧，剛好第11名？結果真的跑超久的，三十多分鐘後答案終於出來了，輸入答案後，出現歡迎畫面，恭喜你是第10名！哈哈，超爽der，撈到個第10名，很久沒拿到前10了。
進去論壇後讀了大家的精妙解答後發現了一件事 ，我可以把某個東西做排序，這樣就大大的降低了所需的運算個數。遇到某一個特定pattern，如果map裡沒有就做運算，再把值存在map裡，如果map裡已有同樣的pattern，就從map裡讀出其值，結果只需要12秒啊！我當初怎麼沒想到要做排序啊？有夠蠢的。
就憑著這個第10名，讓我又回到歐拉人(Eulerian)的第15名。日本第3！第一名為Min_25(1)，第二名為uwi(7)，第三名是我utomaya(15)
其實這張表格已經是比完ProjectEuler第642題後的積分圖了，ProjectEuler#633~#642這十題的recent problems，我五次最好成績分別為第10名(#636)，第14名(#639)，第15名(#642)，第19名(#639)以及第19名(#633)，總分178分。
沒有留言:
張貼留言