ProjectEuler 535 Fractal Sequence - Solution

題目在UTC17:00發布。因為有本週是困難題的預期(後來證實完全是誤判)，所以一開始就沒積極搶攻，加上一時沒有任何思路，所以先進入觀戰模式，三十分鐘過去了，看了一下fastest  table，很好！沒半個人解出來，果然不是簡單的題目。然後一個小時咻的一下就過去了，再看了一下fastest  table，很好！沒半個人解出來，果然是困難題。按照過往的經驗，第一個解出來的人若是落在一小時之後，大約要6、7個小時後才會有20個正解者；甚或十幾個小時後才有第20個正解者。由於我實在是個弱菜，目標拼前20就好，所以決定慢慢解。(後來證實是個誤判，1小時13分才有第一位正姐，但3小時39分就有第20位正姐了。)


一如以往的一開始很懶，只想用紙筆找到公式 ，不想寫太多行程式(我的壞習慣)。一邊用紙筆往一些無關緊要的方向去走，例如列出數列到第63、64項吧 - 我想，一邊視察著fastest  table，咦？不對。怎麼一堆人刷刷刷的都過了？開始有點緊張了！ 怎麼辦？我一點進度都沒有欸，剛才fastest table完全沒動靜原來是早就有一堆人在鴨子划水了。好吧，先求出小數據吧。也就是先求出T(10^9)看是不是 498676527978348241再看看要怎麼兜吧！

一時緊張，竟然要怎麼用程式輸出數列的前幾項都不知道怎麼寫了？咦！用紙筆列不是很簡單嗎？怎麼程式寫這麼難？不貪心，先列個1000項就好了。然後手賤一直去看fastest  table。不看還好，愈看愈緊張，已經有7、8個過了。這下子又要二、三十名了嗎？不行，要冷靜、冷靜！冷靜才能成大事。後來想想，好像沒那麼難！既然是fractal sequence，也就是自己能產生自己，那就定義兩個陣列a跟b；a跟b其實都是題目提到的同一個數列，但b由a產生，產生的方式就是由a不斷的插入circled numbers，所以b一定比a長(或跟a一樣長)。然後a的第n項再由b拷貝過來。a的第一項a[0]當然就是1。這樣就可以列出數列的前n項了。b的陣列開多大，就可以列到第幾項。

然後再想到每一個non-circled numbers b_i必須插入floor(sqrt(b_i))個circled numbers，靈機一動，或許只需要求到數列的N^0.5項，就可以求出T(N)。而且circled numbers都是連續的，相當便於計算，只要記住前一項b_i-1必須插入的circled numbers的最大值C_i-1，那麼b_i-1跟b_i間要插入的circled numbers的總和為(2*C_i-1+1+floor(sqrt(b_i)))*floor(sqrt(b_i))/2，且C_i=floor(sqrt(b_i))+C_i-1。

換言之，只要求到數列的10^9項，便可以求出T(10^18) ！但這個算盤未免打得太如意了，經測試後，必須求到1325208項，才能算出T(10^9)，其關係約為N^(2/3)。也就是要求出數列大約前1.3*(10^12)項才能算出T(10^18)。完全不可能，我電腦沒有這麼大的記憶體。就在這時候，已經有15還是16位解出來了，原來有這麼多人都划到終點了，我才划到一半欸。這時忽然有一種感覺，前20應該無望了。可喜可賀的是至少求出了小數據T(10^9)，跟題目給的hint數字完全吻合。

約莫過了數十分鐘，我又想到了，如果再插一次circled numbers呢？連插兩次circled numbers，複雜度約為(N^(2/3))^(2/3)=N^(4/9)，理論上只要求到數列的大約1.69*(10^8)項，就可以求出T(10^18)。等於由b數列自我產生一次數列後再自我產生一次數列，等於連插兩次circled numbers。保安！保安！可以讓人這樣插了又插，插了又插嗎？咦...好像可以欸，仔細想了一下，技術上好像是可行的。我電腦雖舊，還是有2G的記憶體，可以開足夠大的陣列產生數列前1.69*(10^8)項。

於是粗略寫了一下程式， 測試T(10^18)需輸出數列到第幾項才夠，細部的部份待會再寫，測試了一下大約需1.67*(10^8)項。這時候又偷看了一下fastest  table。唉，已經20位解出來了，那就20幾名吧！

然後細部的程式，又花了一些時間寫，又是一堆bug不斷的調，等調校好的時候，T(10^9)也能正確無誤產生的時候，開始試跑需要多久的時間，好像N每增加一百倍，時間增加10倍左右。T(10^14)約4.7秒，T(10^16)約55秒，這樣看起來T(10^18)約需十分鐘。由於要跑很久，在跑程式之前作了一番檢查，這時候又看了一下fastest  table。已經有23位解出來了。檢查程式沒有錯誤就放行了，我則是趁電腦跑程式的時候看了一下電視，約莫十分鐘後回來，把答案上傳，完全正確！第24名！中間沒有任何人插進來。就這樣，以24名作收。

然後再看一下fastest table，aleksey跟x22還是一如以往的快， 永遠能在前20，grechnik吊車尾進前10，TooSimple第3，不愧是Codeforces排第4、TopCoder排第8的高手。然後有一位新朋友steffen19w23第一次進到前10。恭喜！11到20都是一些老面孔，uwi身為CodeChef short兩小時半的時間能解5題的高手卻在這題花了將近3小時只排到第15，有點不給力(還是去參加了別的比賽才又回來解？)。我還是一樣的弱，只排到第24。在我之後3小時32分47秒後才有第25位正姐。我的提交時間往前推3小時32分47秒後可以追到第11位正姐了，差真多。

總結一句話，這題並不難，算不上是困難題。

這題我單題排在24位，Eulerians排行也剛好排在第24位。