2018年8月18日 星期六

2018 Facebook Hackercup Round 3 流水帳

由於前兩年都進了 Facebook Hacker Cup 的 Final,所以壓力有點大,因為我向來自詡自己能到達的階段是不太會退步的 XD

開賽時中規中矩的從 pA 開始看。今年的題目似乎比往常的短很多,也比以前還要容易理解,但這題就算理解了題目,也是沒什麼想法呀...,想了幾分鐘後,就決定想到什麼就寫什麼,例如說:我想到了若有連續三個井字號,則這三個井字號以及後面的字源可以全部不用理會。又或是若有連續兩個井字號,下一個字元不是星號也不用理會。

總之就是想了各種條件,大概就是又分成答案是 $0$、答案是 $1$、以及答案大於 $1$ 的 Case,其實也就三種 case 啦...但是真的很難想的清楚,所以我提交時已經過了 45 分鐘了。

但以開場來說,這個速度其實還算正常,我是第 30 個提交題目的人,但真的正常嗎?這也很難說,因為可能其他人不僅已經提交了一題,而且還把所有題目看完了,但我剩下三題都還不知道題意。

接著我選擇看第二題,題目理解後沒什麼頭緒,說是沒什麼頭緒也不對啦,總之一定有複雜度超高的 dp 方法能做,但實在是高過頭,想了一下對於壓低時間複雜度的方法毫無頭緒,於是決定先看第三題。

第三題讀完我腦中就猜了個 Greedy 類的做法,感覺還蠻對的,但沒有仔細證,可是時間複雜度是 $O(N^2)$ 而這題 $N = 30000$,嗯...依照 Hackercup 過去以來的尿性,真正 $N$ 是滿的測資其實很少,相信 O(N^2) 也是能過的!於是我就直接寫下去了!但為了讓心裡更有底些,我在寫的過程中,同時也想著要把常數壓小,導致雖然做法簡單,但還是寫了很久,終於寫完後,卻發現我 Sample 錯掉了!!!

這可怎該怎麼辦?看來看去,都覺得我的程式碼寫得很穩呀,到底是哪裡寫錯,還是有哪裡想錯了?仔細分析了一下挫的那組測試資料,實在是看不出所以然...

這時比賽只剩約 70 分鐘...完了...完了...感覺一切都完了...但我還是繼續拼命地動腦 QwQ

我一直在想著,我的 greedy 方法到底拿理會錯調,想著想著,我突然靈光乍現,想到一個更穩妥的 dp 方法,雖然一樣不知道是不是對的 XD 不過它超好寫,於是我迅速的把它揉完,並發現 Sample 因此通過了,也沒時間再驗證做法正確性了...總之就傳吧 (>__<)

看了一下 scoreboard,我大概落在五十幾名吧...而且只剩一個小時左右了,這時才開始讀新的一題並且想+寫感覺時間不夠呀...但是第四題這時有好多人傳了喔...感覺不寫第四題說不定就沒機會晉級了...所以我開始看第四題,繼續把第二題擱著。

第四題讀完後覺得不得了不得了,這題的感覺和 tmt514 在今年某場比賽初的某題有 87% 像呀... 於是我先想了一下下正確性到底如何,但是...感覺時間不夠讓我好好證明 tmt514 用的方法是不是可以直接套用在這題上了,但感覺就是很對嘛!於是我就把之前那場我寫的程式碼找出來,改了一下後, Sample 就輕鬆全過了...就直接傳了吧,傳完後我的名次就進到前 25 名了。

剩下半小時,我還是努力有想要寫出個 pB 的代碼,所以我也是想到什麼就寫什麼,但是寫到剩下 5 分鐘時,發現我寫的方向錯掉了,很難修正...於是就放棄了 Orz,剩下時間就盯著 scoreboard 看。其實這個時候我的名次已經遠遠掉出 25 名外很多了,但我真的沒辦法在做什麼了吧 (>__<) 就一直觀察著我的名次我後落...

四點一到, score board 刷新後,發現我竟然三題都通過了!!!勉強的重新回歸前 25 名!這真是太令我感到意外了(?)我...我...就這樣又進到 Hackercup finallist 了 (>_<) Facebook 的出題群是不是要檢討一下呀 XD 連三年都讓笨笨如小月我這樣的人水進 final XD