【World Finals 團練紀錄】2012 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
這次認真印了三份題本和 codebook 並禁止大家分心來不要浪費 World Finals 的場，我自己也有準備食物，想題過程是沒什麼問題，但實作不知道為什麼超乎預期的糟⋯⋯總之先記錄下來再說。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/3/31 13:11~18:11
$\color{gray}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{green}E$ $\color{green}F$ $\color{red}G$ $\color{gray}H$ $\color{green}I$ $\color{gray}J$ $\color{green}K$ $\color{green}L$
Penalty：1189
Rank(versus official)：4
題目
比賽過程（省略題目敘述）
開場我老樣子設環境，結束之後隊友都還在讀題目，我就撿了在計分板上莫名有人 -1 的 D，看完直覺覺得是不難的題目，但剛開場腦袋有點卡，沒有直接的想法。轉而接著看 E，$n\leq 75$ 感覺是需要很暴力的題目，短期也想不太到好做法。看到鄭忠宜剛好讀完 H 我又順便問了一下他題目意思，聽完之後雖然感覺不難但好像細節很多。瞄到 F 發現是王炳豐在 2019 國培丟給我們的題目，但我跟蘇柏瑄都一致覺得自己忘了也先放著XD
沉寂了一陣子之後發現 B 有人傳，剛好蘇柏瑄漏了這題就趕緊撿來讀，讀完發現就是個積分白痴題，不過有關於輸出到底是不是四捨五入有點爭議（古代 World Final 的題敘也是不太嚴謹Orz），所以我們打算先再觀察狀況一下再寫。
同時我又提出 D 應該不難就讓蘇柏瑄想，他意外的很快就差不多做完並講出一個讓我同意的做法，但在這期間 B 陸續的被越開越多，狀況告訴畢竟 D 有細節，我們應該就先開 B，簡單討論一下我就開寫了。
B 雖然水但要寫兩三個繁瑣的簡單東西就多花了幾分鐘，期間蘇柏瑄看到 C 被開掉去讀完之後就說自己會做了，而鄭忠宜也在一旁說他會做 K 了，所以這時候我們有四題在大卡 queue，開場讀題順序意外的錯一坨，這應該只是運氣不好吧XD
等我寫完 B 之後 de 了一小下白痴 bug，傳上去成功一發。
--pB AC 0/30
蘇柏瑄接著決定來寫感覺比較穩定的 C，而我在旁邊聽鄭忠宜講 K 的做法。
討論 K 的過程意外有點鬼打牆，不知道為什麼我們溝通超久，這時候我自己的精神應該不錯但不知道為什麼遲遲進入不了狀況（
不過因為 C 寫得有點久我們還是把 K 討論到差不多定案了，等蘇柏瑄寫完之後一傳
--pC RE
居然吃 RE，很早就吃 penalty 讓我不是很舒服(X
不過蘇柏瑄看起來馬上就對自己的 RE 有想法了，因為八成是中 assert，而剛好我也需要思考 K 的細節我就沒搶走電腦讓他改，他多測一下改改再傳就過了。
--pC AC 1/52
接著換我上來寫 K，不過因為這些題目的輸入是到 EOF，雖然我們是說就當單筆測資來估範圍，但我還是很怕會被多筆測資的例如值域重設搞到 TLE，就多花了一點時間特別處理離散化的各種 issue，中途卡了一下讓蘇柏瑄上來寫 D 要用到的 Z-value，但寫完之後又錯範測。
卡 bug 的同時鄭忠宜在一旁表示他覺得他可以在多項式時間內把 3-SAT 歸約到 E，因此蘇柏瑄就幫忙多看了幾眼題目，發現題目的圖是競賽圖，頓時變得很能做。
幸好寫完之後抓完範測的問題就無懸念的過了。
--pK AC 0/76
這時候老實說我覺得我們開題有點慢（主要是做題順序上有點糟），不過跟現場對比起來其實沒有說多差，當然我的直覺告訴我這個速度跟現在的選手比起來應該還是慢上不少，但還是別太在意比較好。
總之在蘇柏瑄上來寫 D 的過程我們趕緊去想其他題，而計分板上 E 很厲害的被現場隊開掉了，因此我認爲這應該是下一題，就開始嘴砲有沒有什麼性質，第一直覺告訴我先猜有沒有鴿籠好性質，但我腦袋還是很鈍（剛吃完巧克力血糖感覺還沒上來）所以決定直接把直覺講出來交給鄭忠宜幫我想，果不其然他馬上就找到性質是蓋最多點的點至少能蓋 $\frac{n-1}{2}+1$ 個點，而這個性質讓我直接想到答案不超過 $\log n$，所以我就唬爛說是不是折半就結束了，鄭忠宜就被我騙過去以爲是水題，我們就自以為做完了。但過一下子回來多想一下就發現不太對勁，我又沒辦法做 FWT，就又卡住。
等到蘇柏瑄寫完 D 一發 AC。
--pD AC 0/87
因為我們兩個明顯只是在卡怪東西，該有的性質應該都有找到，蘇柏瑄就加入來看這題，幫忙仔細估一下之後我們發現其實答案不會超過 6 個點，而 $75^5$ 看起來是一個能過的複雜度，就直接開寫。
這題我自己覺得我的實作方式很乾淨，先 greedy 一遍找到 6 個點的答案後才開始用遞迴暴搜，暴搜過程看到超過當前最佳解就剪枝，這樣的好處是如果我們的分析有小錯誤也頂多吃 TLE 不會吃 WA。
很開心的一發解決了。
--pE AC 0/110
這時計分板告訴我們 pL 可能是下一題，鄭忠宜就講了一遍題敘，是一道賽局怪題，非常詭異，我們連構造到輸入上限的測資都一時想不太到，不過多想一下我就構出來了，但依然沒什麼幫助。
這題可以說是我們隊的硬傷，我們三個可能交替都處理了這題一段時間，但都沒想到什麼做法，過一小段時間我就覺得不太對勁，催促隊友去讀 F 跟 I。
蘇柏瑄表示他有在想 F，而鄭忠宜跟我們講完 I 之後感覺就是一道不難的題目，多跟蘇柏瑄嘴砲一下就差不多做完了，雖然實作量有點大，不過我們現在沒題目寫我就上去開寫，並請蘇柏瑄在旁邊手寫他宣稱是大 case 樹 DP 的 code（我自己覺得那種東西先手寫比較穩）。
這裡我的腦袋意外的挺清楚的，意外的大概花二十幾分鐘就把兩百多行的 code 打完，雖然範測輸慘但程式架構還算好 debug 就沒有太慌。
debug 到一半蘇柏瑄和鄭忠宜在旁邊猜了 L 的做法，就趁我去上廁所的時間切過來先寫，回來看到他們差不多寫完丟上去
--pL WA
可惜沒過，因為已經一陣子沒開題了，我們在計分板的位置就一直逐漸往下掉QQ
多抓了快十分鐘的 bug 後終於換我傳 I
--pI WA
又吃 penalty，我自以為實作挺清楚的（
但多想一下根本就是我忘記開 long long，改掉再傳
--pI WA
還是錯，其實我有偷偷因為 CF 很快 WA test2 懷疑應該還沒戳到 long long 的問題就錯了，不過因為是非法資訊蘇柏瑄又說服我這隨便構都有我就還是傳，然後就吃 WA。
而此時蘇柏瑄就把我趕去旁邊盯 code 他上來寫 F，我盯了好一陣子之後發現我根本就是在最後一刻 code 寫累了才同時忘記要開 long long 以及忘記處理取答案 min 的問題，我就切斷他上來補上後者，多看一下沒問題就傳。
--pI AC 2/222
才終於 AC，但時間也剩不多了，雖然剛剛看起來沒做什麼事，主要是 L 真的耗掉我們不少時間。
因為 L 還是沒什麼想法我就請鄭忠宜去讀 G，讀完之後我想沒幾下就覺得我做完了，跟他講完做法之後他也沒辦法反駁我，但計分板上超少隊開出來，所以我覺得很詭異，我的做法甚至沒用什麼高科技，就一個 $O(V^2)$ dijkstra 而已，而且感覺也不難寫。
等蘇柏瑄寫完 F 之後，我表示我們信任他的樹 DP 能力就催促他傳，開心一發 AC。
--pF 0/250
我就請蘇柏瑄去再讀一次 G，因為我很擔心是題目被看錯，他讀完之後我跟他講完做法他也覺得沒問題，時間又不多了我就趕緊開寫，他們兩個在一旁討論 L。
G 寫完之後我抓了又進入 debug 階段，而蘇柏瑄他們決定上來為 L 加一段唬爛 code，反正時間也沒很多了。
--pL AC 1/282
結果意外 AC，但他們完全沒有頭緒為什麼加了就會過，他們只是構出原本做法的反例之後再硬加東西判掉而已XD
接著壓力都到我身上來了，全部人開始幫我抓 G 的問題，先是過了範測然後
--pG WA
多被蘇柏瑄抓到一個問題後我改掉一傳
--pG WA
發現我剛剛加的東西在耍笨亂寫一通，再傳
--pG WA
然後就沒有然後了，卡 bug 到最後QQ
結語
1. 結束當下抓 G 的 bug 發現是 $O(V^2)$ dijkstra 沒加 vis，永遠都在用同一個點 relax，蛤？這種 bug 也可以錯⋯⋯而且因為兩個隊友不知道為什麼都對 $O(V^2)$ dijkstra 的 code 沒什麼印象所以都剛好沒抓到，也太慘了吧（
2. 承上，所以連續兩場 WF 模擬都在最後卡一題白痴 bug，好慘啊
3. 賽後我們也同時在嘴砲 A，我表示如果最後一小時沒事做且剩 A 我應該會上去唬爛，而看了官解之後意外發現這個唬爛能過的可能性很高，應該說他根本就是跟官解差不多的東西，精神 + 一題。
4. 稍晚吃飯跟鄭忠宜又隨性的嘴砲完 H，也跟官解差不多，精神又 + 一題，上一場也是這樣被我們嘴砲到剩一題，所以古代 WF 的題目老實說也沒有多難，就是我們寫好慢（
5. 總結來說這場除了 L 是戳到我們的弱點外，其他問題幾乎是發生在實作穩定度特別差身上，這兩場 WF 模擬的 penalty 都意外的多，實作穩定度到底發生了什麼事啊⋯⋯8BQube 的題題一發魂呢？希望能抓回實作的手感
6. 發現這場也忘光要在第二個小時釐清整場比賽的題目，上一場的檢討只有記得要給隊友看自己抄的模板而已，下次千萬要記得
8BQube 加油！
留言
張貼留言