這已經是我第七年參加 Code Jam了，並且是連續第五年進入 Round 3，雖然乍看之下我可以很穩定的進入 Round 3，但離進入 Onsite Round 還是差好遠啊... 好似已到達了自己的極限，難道沒有辦法有哪一年來正正常常的去一次 GCJ 或 TCO 的 Onsite Final 嗎 >_< 像去年那樣因為出很多SRM題而被邀去現場的機會沒有也沒差啦 >_< 一直以來的夢想都是身為參賽者好好的去現場比賽，而不是只是去觀戰啦 >_< 好啦碎碎念到此... R3 就要開始了。
看了一下今年題數和每題題分，今年總共有五題！？以前從來沒有那麼多題過吧！(事後證實這是我開始參加GCJ以來頭一次，以前都只有四題) 題分總和依序是 12、13、23、25、27。這是有兩題水題，讓基本分提高的意思嗎？看來前兩題是一定要得分了，於是我從第一題開始看。
第一題是給一個 Rooted Tree，每個 Node 都有一個值，我們要找出盡量多的與 Root 連通的 Node，使得這些 Node上的值最大與最小的差不超過 D。數據是使用 Random Seed 產生的，小測資 $N \leq 1000$、大測資 $N \leq 10^6$ ，大測資 $N$ 那麼大啊... ，看來若要使用 dfs 要小心了 (有記得之前 Facebook Hacker Cup 的教訓)。
小測資讀完題就知道怎麼做了，枚舉所有被選的 Node 的可能區間，從 root 去 dfs 看看最深能到哪，並把走過的點都選起來。大測資的話.... 嗯... 動態樹可以解決吧...? 可是我不會動態樹，並且也沒有動態樹模板 OAQ 但我還蠻相信這題有很簡單的作法的，於是繼續想下去，是說 ... 這真的事最簡單的一題嗎 >_< 這也太難了吧！！！以前的 GCJ 每個 Round 的最簡單一題我幾乎都能看到就知道怎麼做吧 @@
十分鐘過去，終於有第一個人傳了 pA 大小測資，是 在 IOI 勝過 tourist 的昔日最強中國高中生 WJMZBMR m(_ _)m，唔唔唔，看來至少這題在 coding 速度而言在想下去投資報酬率是 OK 的吧？想到了應該能很快寫完。
嗯... 這題八成還是要枚舉過所有可能區間，重點就是當枚舉某個區間時，匯有某些 subtree 的點會全不排除在外，也就是要知道每個點在什麼時候會被當成 subtree 的 root，一個點要被當成 subtree 的 root，代表他的所有祖先都有被選到，也就代表該點的值，要不是筆所有祖先的值都還小，就是比所有祖先的值都還大！嗯！這樣子再下去就能做出來的感覺！於是我決定值接開始寫 code了，邊寫邊想，並且先順手寫了一個 $O(N^2)$ 的 code 來作樸素對拍。
大概三十多方鐘時我把能處理大測資的 code 也寫完了，但是對了一下小測資的答案和 $O(N^2)$ 的方法不一樣 OAQ Why OAQ 於是我開始漫長的 debug，時間消耗的很快，比賽已經經過了一個小時，我仍不知道我的 code 錯在哪。
唔唔不行啦 OAQ 比賽只剩下一個半小時，而我就只為了這僅僅的 9pt 卡在這，這不是明擺著沒救了嗎？於是我捨棄了想找出 Bug 的心情，決定先搶搶其它題小測資的分數，順勢看看有否可以有所作為的題目。看了一下 score board， pD 的小測資應該是其它所有題目最簡單的吧？
讀題...讀題...讀題... (卡住的狀態)。可惡啊，是因為前一個小時比不好太焦慮了嗎？為什麼 pD 最後關於符合條件的答案時要選擇哪組答案輸出的條件我怎麼反覆看幾次都還是看不懂 @@ 這題不過就是那個有n個數，給任兩個數得和的 set，還原這 n 個數的變型吧？感覺作法就應該會差不多嘛。看了一下小測資的條件：所有數都非負。在這個條件下肯定是唯一解，所以那個多組符合的答案要優先輸出什麼就不必管了 >_<，所以就快速把小測資 AC 掉。
已過 1 小時 17 分。AC 掉 pD 的小測資後，由於還是不懂多組答案要優先輸出什麼，所以就決定先捨棄大測資，去看 pB。讀懂並想了一下後 ... 唔...感覺上小測資沒有比較簡單的方法啊？雖然我想到了一個作法，可是這個做法應該並不簡單耶...? 唉唉唉不對啦，這個作法連大測資都可以在時間內跑完啊 = =，於是這題就直接寫大測資了，邊界加減一的地方稍微卡了一下，但還算蠻順利的就 AC 了小測資，這題小測資過了感覺上沒道理不過大測資，就直接傳了。
已過 1 小時 40 分。若有心還想進 final 的話... 我現在應該要...唔怎麼想都覺得沒救啦 >_< 從 score board 看來，A、B、D三題都 AC的人將會滿街都是，而在我 pA 沒有大測資的分數情況下，一定得靠 C 或 E來追分吧？稍微看了一下 C，感覺題目好常似乎會不好懂 0.0，於是反回看 pC。
pC一臉就 O(N^3) dp 樣吧？可是...可是...他的順需要怎麼排？想必不能值接按照最初的座標順序排呀，那按照速度關係排呢？唔...感覺上不好想 or 要想清楚不簡單耶 ...，那就還是先把小測資水一下吧。
小測資 $N \leq 25$，第一個閃過去的作法就是 O(N^2 * 2^N) dp，但 N 高達25耶 ...，我沒把握四分鐘跑的完，於是再多想一下，嗯...枚舉每追到一個寵物後，下一步要往左追還是往右追，這樣的話就是 O(N * C(N,N/2))，這個複雜度就很 OK 了！之後順利的把 AC 小測資 AC了。
比賽經過 2小時 4 分鐘，還剩下 26 分鐘， C 和 D 的大測資感覺上都不太能在剩下的時間處理，而下就算處理完得分也不夠高，不足以逆轉結果。最後能拼的就是在剩下時間把 pE 小測資連同大測資一併解出了吧 OAQ。
又經過了十分鐘，我還是沒有把 pE 題目看懂 OAQ 看來這場已經註定沒救了啦 OAQ 就算大家大測資都 fail，我小測資也沒有寫的比別人快啊！剩下 15 分鐘我還能做什麼呢？
雖然心以死，但是我還是盡可能的利用剩下時間吧，回去 de pA 的 bug。在比賽剩五分鐘的時候發現我哪裡想錯了，而且只是發現哪裡"想錯"，並還沒想到要怎麼改才是"對的"，五分鐘覺對不夠用了啦！
比賽結束，小月(Kirino)排在第 123名 (其實我覺的沒進 final 的話第幾名都不是很重要，因為我只要使用快速讀完所有題目並把所有看得懂題目的小測資都先做，名次一定不低啊?)，結束了今年度的所有賽事(雖然 TCO 今年只取 12 個...我覺得值接認命去當兵吧 0.0)，今年也是一事無成啊 OAQ
恭喜皮皮 (peter50216) 總算是進到 GCJ 的 final，過去好多年雖然皮皮都在 Round 2表現超好，可是他在 Round 3都非常可惜 >_< 也恭喜新竹實驗中學的 betaveros ，在高中就進到 top 25超厲害的 >_<，還有凱琪也排在第三十名，之前有候補到 30 名以後，今年前 25 名也有好多無法去 final 的未滿 18 歲的人，說不定有機會候補上>_<
唔唔後年再加油吧 >_<
沒有留言:
張貼留言