【World Finals 團練紀錄】2014 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
終於度過了漫長的蘇柏瑄國軍日，在他回歸之後打了兩場回手感就來刷一場 Finals。可惜這場大家開場前好像就有點想睡覺，雖然可能有微微影響，但應該還是有更多值得檢討的地方。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/8/29 13:31~18:31
$\color{green}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{gray}E$ $\color{gray}F$ $\color{green}G$ $\color{gray}H$ $\color{green}I$ $\color{gray}J$ $\color{green}K$ $\color{gray}L$
Penalty：1341
Rank(versus official)：1
題目
比賽過程（省略題目敘述）
開場快速設完環境之後，因為題目閱讀量不小所以讀了好一陣子題目，計分板也沈寂了十分鐘左右，這時 K 被開出來了，是鄭忠宜讀的，但他說他還不會做，結果我一聽我就用倍增精神秒了，雖然可能可以更快但感覺就不需要。
因為沒其他題做我就開寫了，在第 23 分鐘時上傳了一發，
--pK WA
又是一個開場 WA，但不慌，總能追回來。
我很快就發現我雙指針爬錯東西，改緊在三分鐘內改完之後再次上傳
--pK WA
...什麼鬼，難不成又要像 2020 一樣的開場（
盯了很久我都找不到問題，有點懷疑是序列複製兩遍不夠，但構不出反例，所以我只好直接把這題丟給 icube debug，我先去想其他題。
一旁的蘇柏瑄表示他覺得他會做 B，但多看一下就發現直接背包會 TLE，他就問我該怎麼做，而我們在 2019 國手培訓的時候其實就討論過這種物件多拿幾樣價值會遞減的問題可以在 $O(W^2\log W)$ 的時間內背包搞定，只是這題算一下會到 6e8，我們不是很有自信，就先放著。
嘗試看了計分板之後發現 D, I 被開了，蘇柏瑄去處理 D，我一問 I 的題目發現是個最大團題，可能要用幾何性質做他，我思考了一下子之後看一眼範圍就發現 n 只有 100，這不是蘇柏瑄的自信 dyn 最大團肯定可以直接壓過去的範圍嗎？
所以我就沒有猶豫的開抄 dyn 了，抄到一半 icube 跟我說 K 有越界存取，我就直接把這個問題修掉之後把序列複製改三遍再傳一次，
--pK WA
好啊沒差，我繼續我的 dyn。
dyn 寫完之後傳上去，
--pI AC 0/51
果然無懸念 15ms 搞定，dyn 神板子。
而蘇柏瑄在剛剛就在很猶豫 D 如果 1e6 * 26 * 26 要不要開寫，但 D 時限 8 秒，他宣稱他常數又很小，我就慫恿他開始寫，我下來 debug 或想其他題。
在蘇柏瑄寫題的期間我嘗試想了 F 跟 G 但都沒想到，K 也盯不到問題，想說等等乾脆直接對拍好了就丟著，而我把剛剛沒做完的 B 拿過來寫了一下式子就覺得這是斜率優化，但我想說等蘇柏瑄寫完。
蘇柏瑄寫完 D 之後一傳，
--pD AC 0/64
就輪到我開始對拍，結果一對就有了，多看一下發現我在笨，一開始雙指針爬錯順序的問題其實還會影響到我後面的 break，必須寫成 continue 才會對。
--pK AC 3/71
怎麼會這麼笨（
K 過了之後看看計分板，發現 C 漸漸有隊伍開掉，其實稍早我們就有在討論需要一個簡單多邊形重心的板子，然後我只會用梯形剖分做所以有點尷尬，結果蘇柏瑄多想一下就宣稱測量師是不是就好了，我一聽覺得超有道理，就直接開寫。
而我跟蘇柏瑄說我覺得 B 就是個斜率優化，他導一導還跟我說裡面有平方項是不是不能做，我一聽就覺得很詭異怎麼可能，直接寫一遍大致的東西給他看說服他之後他就乖乖回去把剩下的式子導完。
C 找完重心之後就剩一個 O(1) 的式子，但我為了全整導了一百年，因為範測錯得亂七八糟所以就讓鄭忠宜上來寫他剛剛在偷做的 A，他說本來想讓我寫但我實在是太可悲了。
前前後後改了好久之後，我才終於改到一組對的係數，改完之後過範測，多檢查一下之後傳
--pC AC 0/130
最白癡的是我們現在這樣四題已經算很慘了吧，結果排名居然是在前面，這場 WF 是有多可怕，怎麼大家都只有 3、4 題。
icube 改完 A 之後發現自己假了，蘇柏瑄就換上去寫剛剛導完 B 的斜率優化，而我因為沒有新任務所以開始看了一下剩下的題目，希望能整理出後期的流程
- A icube 在做，期望他能做完
- B 做完了，蘇柏瑄在寫
- E 看起來可以做，但我很沒概念，應該要等蘇柏瑄下來討論
- F 有機會做，但應該是一個很後期的幾何題
- G 看起來可以做
- H 不太清楚，但應該不好做
- J 看起來不太好做
- L 問了 icube 之後感覺是後期沒題目做就會收掉的題
這樣順利的話預期最後可以 8~9 題，我大致決定了方向之後就開始決定來做 G，感覺是一個乾淨結論的猜。
不過仔細思考之後，越想越覺得不太對，我就開始朝著枚舉一些東西的方向去想，過一陣子蘇柏瑄寫完 B 了，一傳
--pB WA
WA 的期間 icube 也在改他的 A，我先切斷了 G 的思緒讓蘇柏瑄跟我討論有哪裡有 bug，唸一唸他就發現他好像擅自覺得答案如果是負的就要輸出 impossible，蠻白痴的，再難吃的題目都應該得做。
改完傳上去，
--pB WA
又吃一筆 WA，雖然 CF 看得到多過一筆感覺是非法資訊就是。
接著就換 icube 回來改他的 code，我回去想 G，多想一下就發現我如果先窮舉 max(D(A), D(B)) 就可以用二分圖判定這是不是可能的，而 min(D(A), D(B)) 多看一下就發現可以想成 2SAT，非常美麗的題目。
不過分析後又發現這樣是 n^4logn，不是很好，但再想一下就會發現我不用每個窮舉 max 都跑 2SAT，二分圖結構有改變再跑就好，這樣 n^3logn，完美。
G 精神完之後我開始在想 F 跟 L 哪一個才是要在最後開的幾何，所以就在想 F，感受到一個點是 messenger 出發的點後感覺是畫圓找到掉在圓裡面的線段什麼的，但這樣複雜度感覺很差，又多考慮了一下之後有種三維幾何的味道在飄出來，我就知道該丟了。
等到 icube 改完他的 A，一傳，
--pA WA
有點太慘（
我就開始寫了一點 G，不過寫到一半蘇柏瑄就覺得他 INF 開不夠大要再改。
確認不會溢位之後就再傳了一發，
--pB WA
還是 WA，怎麼會（
我回來寫 G 到一半蘇柏瑄就開始在碎念自己怎麼有一個不重要的判定沒順手改掉，而且是一個感覺很不容易發生的浮點數誤差 issue，他就很糾結到底會不會錯這個，糾結到 icube 被他抓過去問一遍但沒概念，我就覺得已經浪費太多時間了，就改掉再傳一次，
--pB WA
果然還是 WA（
後來等到我 G 寫完 + debug 完後我也傳
--pG WA
蘇柏瑄頓時就笑了出來，這場怎麼這麼躁(X
不過我馬上測點小測資就找到自己的問題，改完傳上去
--pG WA
但 WA 很後面，我就下來讓 icube 改他的 A，我盯著我的 code，多看就發現我在檢查當前窮舉的 max 有沒有用的做法是戳下一個要窮舉的數字會不會影響二分圖結構，但我只戳了一條邊，應該所有邊權一樣的都要檢查。
改，再傳，
--pG AC 2/251
終於在封板後拿下了 AC，但幾何就是不能開了，我跟蘇柏瑄說接下來能的話就是要開 E，他也說他有點想法，但我完全聽不懂他的想法是什麼，可能這種題目對我來說就是超級難想像，太玄學。
我就跟他說現在的最佳策略可能是我去抓 B 的 bug，他去想 E，他也同意之後我就開始盯。
而 icube 又改完一次 A 之後再傳，
--pA WA
一樣對的變多了，實際上這個 A 是一個構造，而答案的下界只能是 n 或 n + 1，所以本地幾乎可以知道會不會過，icube 剩一個 case 是 n + 1（n=3），錯了表示下界肯定都是 n。
我就說他要不要直接寫爆搜，這是最乾脆的，多說服了幾下之後他就乖乖開寫了。
我多盯了 B 的 code 一陣子之後，開始問蘇柏瑄為什麼裡面 dp[i] 轉移 dp[i] 不會是 dp[i]，他就愣了一下發現真的不太對勁，我們一起看了他的式子之後就發現他不會導式子，趕緊上來改一下之後一傳，
--pB AC 4/273
終於過了（
這時候就是等 icube 的 A，而蘇柏瑄大致會做 E 了，我聽完之後覺得有道理，也是我一開始直覺的方向，感覺跟他前面抽象的想法差多了，就讓他趕緊手寫點東西準備接著寫。
等到 icube 終於慢慢改完 A 之後上傳
-- pA AC 2/281
蘇柏瑄就火速開始寫 E，我們預期 18 分鐘是有機會飆完的，可惜最後測了範測全是 0，在搞不清楚的狀況下在最後 30 秒蘇柏瑄發現輸入的變數就用錯了，我叫他改完就傳，他卻改完之後回頭刪了 cerr，結果最後在賽後一兩秒才傳上去，吃了 CE。
結語
1. 後來 E 改了六分鐘之後就過了，實屬可惜，如果 B 沒耍雷應該就能過了。
2. 我同時也說我們 debug code 用 cerr 一部分原因可能就是為了壓線能直接傳，所以跟他說之後這種情況就別刪了。
3. 因為 I 板上過的狀況實在太慘，賽後看了狀況發現確實一堆人砸一般最大團板子 TLE，上網看了別人寫的題解就發現這是套路的最大團 => 獨立集 => 二分圖匹配的對應，應該不是想不到，但 dyn 就是爽(X
4. B 居然網路上有人說先做我們那招 W^2logW 的會跑很快沒問題，怎麼會這樣，早知道寫這個我們就更快解決（
5. 如果沒出什麼事的話，感覺最後穩穩開完 E 之後去做 L 是沒問題的，應該可以 9 題，不過本來就難保穩定就是。
6. 這場真的好可怕，到底為什麼打這樣還在前面。我們討論一下覺得這場細節太多了，很搞人心態，可能因為這樣大家都打得不是很順手。
7. 希望之後練習前能睡飽，不知道我們幾個精神狀況不佳到底影響了多少 QQ
8. 這場策略上應該沒問題，我中期就有大致了解過題目應該真的有搞清楚狀況，大概就一直出包的問題而已（
8BQube 加油！
留言
張貼留言