不知不覺ProjectEuler已經出到第666題了！
666 - 魔鬼的印記
但題目卻不是那麼魔鬼，剛開始像是墜入五里霧中，了解其原理後才發現意外的簡單。不過就是列式子外加疊代，大約只要50次的疊代就可以達到14位的精度。題目只要求8位的精度實在太低了-_-
附帶一提， 這題刷新了我在fastest table的最低名次，第97名--__--
2019年4月24日 星期三
2019年4月2日 星期二
ProjectEuler 663 - Solutions
這題大家都說要用線段樹(segment tree)，可是我不會用啊！我當然知道線段樹，只是不知道要如何將線段樹用在這題？
觀察到要更動的項數很少，大約是2*10^5項，忽然想到區間查詢可以將 陣列分割成Sqrt(N)個區間來做。對於S(N,m)-S(N,n)有著(m-n)*N^0.5的複雜度。依題目的要求，大約是6.3*10^8的計算量。最後程式跑了15秒！1分鐘以內，算是達標了！第23名。就憑著這23名，讓我又回到歐拉人的前20名。175分，歐拉人第15名！！！
觀察到要更動的項數很少，大約是2*10^5項，忽然想到區間查詢可以將 陣列分割成Sqrt(N)個區間來做。對於S(N,m)-S(N,n)有著(m-n)*N^0.5的複雜度。依題目的要求，大約是6.3*10^8的計算量。最後程式跑了15秒！1分鐘以內，算是達標了！第23名。就憑著這23名，讓我又回到歐拉人的前20名。175分，歐拉人第15名！！！
訂閱：
文章 (Atom)