【World Finals 團練紀錄】2011 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
首度打完一場 Finals 之後才覺得好像應該認真看待 virtual Finals 的練習過程，有點可惜這場打得不是很專心，不過也有值得檢討的地方，希望透過這些紀錄我們可以從中反省並逐漸進步。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2022/12/16 13:15~18:15
$\color{green}{A}$ $\color{gray}B$ $\color{green}C$ $\color{red}D$ $\color{green}E$ $\color{green}F$ $\color{gray}G$ $\color{green}H$ $\color{green}I$ $\color{green}J$ $\color{green}K$
Penalty：1061
Rank(versus official)：1
題目
比賽過程（省略題目敘述）
開場我設好環境之後，鄭忠宜馬上就送給我了 pK，一看就知道是一題裸的凸包最窄寬度。
因為計分板看起來沒什麼動靜，加上隊友一時也沒找到水題，因此我決定直接開場就來個旋轉卡尺。
--pK AC 0/12
如預期的差不多 10 分鐘收掉，可惜因為傳上去前有多想一下會不會有問題就沒搶到全場首殺（首殺 11 分鐘），不過也罷，這個算是我們的做題策略。
接著我們看了計分板，目前被開掉的是 E 跟 K，剛好因為 E 題敘比較短被丟到我面前我就開始看，而蘇柏瑄表示 C 可以寫就先讓他上機。
E 看完之後我沒有秒掉，因此直接切去鄭忠宜想丟給我的 J。
J 只是一個需要照順序 dp 的簡單背包，因為規則有點麻煩，跟鄭忠宜確認完細節之後就跟蘇柏瑄說我等等可以寫。不過蘇柏瑄表示我這題聽起來比較快就先切給我。
我上去先做點計算之後發現記憶體很危險，不過因為需要存的數字範圍是 short 存得下的我就輕鬆壓了一半的記憶體(X
不過這題需要照順序的原因就是因為要回溯，回溯寫一寫我才發現比想像中複雜，寫完測下去還直接 RE。
Debug 的過程就切一半螢幕給蘇柏瑄繼續刻 C，交替一兩次之後確認沒問題就傳。
--pJ AC 0/44
寫得有點久，但其實看了一下計分板其他隊伍也都差不多這個時間附近開第二題，不是大問題。
電腦還給蘇柏瑄後鄭忠宜跟我說他不會 E，因為他不會資料結構，但他說他覺得座標範圍很小很有用。
於是正當我想有道理，不應該讓他想這麼久時，剛跟他嘴砲完日本銀河戰艦 13 分鐘開掉怎麼可能會很複雜，他就表示他突然覺得切比雪夫之後前綴和就好了。
於是這題就突然被精神掉了（？
因為 E 大概做完了但還得等蘇柏瑄寫完 C，就繼續看有人過的 A。剛看完還以為亂 greedy 可以過，但多想一下就發現這是大唬爛，還沒有什麼直接的想法。
蘇柏瑄在若干分鐘後寫完 C，再做一點測試後上傳
--pC RE
他說因為他有 assert 東西，應該是某些假設爛了。於是就把他趕去隔壁 debug，我上來寫 E。
E 因為真的不難寫所以我也是迅速寫完，結果沒過範測，抓了一下 bug 修好一傳
--pE WA
連兩題吃 penalty = = 但因為我們今天心態也比較輕鬆就沒急，雖然我們呈現兩個人不知道自己什麼的狀態。
首先想到可能哪裡有問題的是蘇柏瑄，所以他邊說自己應該是不會寫程式邊上去做修改，他改到一半就換我發現我不會寫程式，該重設的東西沒有重設乾淨@@
雖然我這邊改很快但我傾向在多想一下有沒有別的問題，所以蘇柏瑄就先改完一傳
--pC AC 1/76
傳完換我上來改，改完之後再想一下沒問題
--pE AC 1/78
現在四題，我們的 penalty 比較不太樂觀，基本上我們在看計分板都是追著 virtual 的隊伍在打
，所以不太在乎正式排名(X
，所以不太在乎正式排名(X
看了計分板後下兩題比較有風向是 A、D 跟 F，於是我們回去想 A，蘇柏瑄去看 D。
A 討論到一半蘇柏瑄請我幫 D 刻個 Dinic，刻完之後他說他好像假解所以只能放在那邊。
我們冷靜分析之後知道 A 可以窮舉 M 的個數後做到剩下「問區間 [L, R] 中 M 進位表示法位數總和最小的數」這種問題，我覺得我看過但一時有點腦袋模糊講不出來，就決定去裝個水讓自己更冷靜的想。
這裡稍微提一下今天的敗筆，因為我其實最近在控制體重，所以肚子餓得特別快，練習中的點心也從巧克力改成香蕉，造成了我其實從第二個小時開始腦袋就鈍鈍的，實在是有點愧待這場 World Final...
不過總之去裝個水總算是想清楚了，就回來跟鄭忠宜講完想法開始寫。寫到一半蘇柏瑄開始對著 F 碎碎念說這是不是斜率優化，然後就問我說他要不單調斜率優化、還要區間查詢轉移來源該怎麼做比較好，我跟他說不單調有動態凸包，區間的問題多加一個 log 總是能解決。但他馬上就說他搞錯了，區間是在唬爛，應該只造不單調斜率優化而已，就請他在旁邊列式。
A 寫完之後多修幾下範測過了，但其實不太放心就多測了一些東西，果不其然抓到 bug。
改完之後傳
--pA AC 0/129
然後我就幫蘇柏瑄寫他的動態凸包，這裡我發現一個問題是我看不出來我們的動態凸包是維護最大值還是最小值，很久沒用了，該寫註解（
總之我宣稱大概是最小值請蘇柏瑄加個負號處理之後電腦就交給他了，我則是繼續被鄭忠宜餵 H。
H 幾乎是被鄭忠宜秒掉的，我就靜靜地聽他證明，而且看 waynedisonitau123 如此快樂的開掉這題就知道 BCC 這條路準沒錯。
順完做法之後我打算等蘇柏瑄寫完 F 之後上去寫，在蘇柏瑄寫 F 寫到一半他跟我確認動態凸包的細節時，我聽到「機器」兩個關鍵字後突然發現一件酷事，F 不就是經典的 IOIC 斜率優化例題 Machine Works 嗎XD
在同時被我跟後方的 ckiseki 嘴砲後，蘇柏瑄慢慢的寫完了他完全沒印象有看過的 F 測範測，結果錯了。
我其實當下就有點懷疑可能是我搞錯動態凸包維護的極值方向了，但我選擇交給他自己看我先開寫 H。
H 寫到一半蘇柏瑄發現他 F 會在動態凸包是空的時候做查詢，所以根本是 UB，還很剛好的沒吃 RE，不過改了之後還是沒變，我就總算提出了會不會把負號拿掉就過了。
...還真的是，動態凸包本來就是在維護最大值= =
修好後一傳
--pF WA
譴責蘇柏瑄在經典題吃 WA(X
放他在旁邊 debug 的同時我繼續寫 H，過一下子他就發現他的最終查詢還是有可能在動態凸包是空的時候做查詢（
改好之後傳
--pF AC 1/162
若干分鐘後我寫完了 H，因為覺得我們吃太多 penalty 了，我就多測試了幾筆，都沒問題就傳
--pH WA
太慘了吧（
但我各種測都找不到問題，後來突然寫說來測點大的就抓到問題了，一看發現是 tarjan dfs 少抄一行，但範測的 BCC 都很少不會遇到這個問題 Orz
好白癡QQ
--pH AC 1/186
接下來看起來比較能做的就是 D 跟 I 了，於是蘇柏瑄突然講了個 D 是不是能線性規劃，我就開始在想好像有點道理，就開抄了。
因為決定要線性規劃後就沒蘇柏瑄的事了他就去做 I，鄭忠宜則是在一旁試著找找看有沒有 D 的正常做法。
刻完線性規劃仔細估變數數量跟不等式數量才發覺好像不太對勁，數量有點多，但不知道是哪來的自信讓我覺得反正都抄了，傳一次線性規劃不虧（甚至鄭忠宜這時候還說他可能有點 flow 的模型了）。
結果範測錯得亂七八糟，debug 到蘇柏瑄都宣稱他做完 I 了得換他讓來寫我在旁邊看。
終於抓完 bug 之後傳
--pD TLE
還吃個 TLE，我就知道線性規劃沒救了。
於是鄭忠宜就開始跟我說他腦中的 flow 模型，講一講之後他發現好像得改成 mcmf，不過點數很少所以應該沒差。
這裡我感覺我已經因為血糖思考能力變很差了，但我直覺上覺得鄭忠宜講的是對的，就選擇相信他。
差不多時間蘇柏瑄寫完 I 一傳
--pI WA
於是他下去 debug，我請鄭忠宜幫我思考建模細節我開始抄 mcmf + 寫輸入。
抄完之後我開始照著鄭忠宜說的建模，建完之後範測一發過，大致上沒什麼問題就傳
--pD WA
直接陷入兩題卡住的危機。我們兩邊又都不知道自己錯什麼。所以我選擇先來利用線性規劃那份 code 對拍。
這其實是一個大錯誤，線性規劃的正確性其實不是對的，這也是我們實際對拍之後發現線性規劃真的會讓變數 assign 成浮點數造成解更好，失策= =，不該亂 claim 有解 imply 有整數解的。
過一下子之後蘇柏瑄想到自己可能會錯的測資上來打就發現問題開始修了，我在旁邊盯著 code 找不到問題，決定等他搞定來寫認真的暴力對拍。
蘇柏瑄在多測了一些東西後上傳
--pI AC 1/274
接著我就火速上來寫暴力，寫完之後終於對到一個真的錯的測資，但也沒辦法理解為什麽會錯，就結束了。
結語
1. 除了餓肚子的問題外，蘇柏瑄中間感覺也常看手機不知道在處理什麼事，以後打 World Finals 場就想辦法用最佳狀態打比較好，不要浪費場次QQ
2. 感覺我自己打 Finals 場看計分板的頻率有點變高，可以減少
3. D 最後發現是 mcmf 抄錯，改完就過了，edit distance 1（
4. 承上，包含 H，抄錯模板真的該死，這裡先歸咎於餓肚子好了，之後不要再犯
5. 用線性規劃真的是很笨，之後應該要先估變數和不等式數量，太多就別試了，還有整數解的題目也不要輕易砸
6. 抄錯模板其實還是有辦法提早發現，事後跟鄭忠宜討論覺得我抄完模板之後不應該是我自己檢查，應該是隊友要幫我看，我自己看會漏（
7. G 後來看完就差不多精神完了，雖然補題 WA 了還沒修好，但感覺如果這次沒這麼雷應該可以跟隊友合力搞定，至少可以打到 10 題，真是慘（
8. 我感覺我全程沒有很知道整套題的狀況，之後團練來嘗試在第二個小時釐清整場比賽的題目看看，更有掌握全局的感覺會比較好
8BQube 加油！
留言
張貼留言