【World Finals 團練紀錄】2015 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
這場突然就水超多，意義不明，然後打好爛，感覺這次是策略上的問題（
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/8/31 13:43~18:43
$\color{green}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{green}E$ $\color{green}F$ $\color{gray}G$ $\color{gray}H$ $\color{green}I$ $\color{green}J$ $\color{gray}K$ $\color{green}L$ $\color{green}M$
Penalty：1393
Rank(versus official)：7
開場才剛設完環境 A 就被開掉了，我跟蘇柏瑄說，他表示他看完了，但他覺得這不是題目，反正切他上來寫之後他花了一小點時間就收掉了
--pA AC 0/7
接著我們就開始老樣子乖乖讀題目，我嘗試撿了比較短的 E 但我看得沒有很懂，就繼續往後看 F，還是看不懂，怎麼會這樣...
但我亂翻了一下其他題看起來都怪噁心的，我只好請蘇柏瑄幫忙讀個 E，因為他感覺像是一個可做的題，我自己努力嗑一下 F。
F 讀到後來還是投降，但感受得出來就是個 BFS 水題，直接繼續餵給蘇柏瑄請他幫我搞懂，然後確實就是水題，所以我就開寫。
寫到一半聽到蘇柏瑄在跟鄭忠宜討論 C 是不是一個費用流題，但他好像覺得模很難建就有點退縮，中途看個計分版看起來百花綻放，隊友們就相繼去抽時間看其他題目了。
等到 F 過了之後
--pF AC 0/36
計分版看起來最多人過的是 D，就問了 D 的題目，一個白癡三維幾何。
蘇柏瑄：「你需要算一顆球被某個高度切掉的時候的體積」
我：「這簡單啊，有板子」
蘇柏瑄：「什麼？反正就式子列一下積分就好了吧？」
我：「不是，是我們直接有這個東西的公式」
所以我繼續寫 D，但我盯了一下公式覺得很怪，怎麼 $h$ 帶 $2r$ 進去不是 $\frac{4}{3}\pi r^3$，盯到直接被蘇柏瑄進來關心發現我在亂看一通，某個 $h$ 看成 $r$，笨死。
上去寫到一半蘇柏瑄開始在旁邊說 C 是不是可以 KM，我慣性的補一句他是 V^3 之後他就在旁邊自己建模了。
等到我 D 過了之後
--pD AC 0/54
我繼續幫蘇柏瑄刻 KM，刻完才換他上來建模，而我被丟了剛剛隊友想不出來的 L。
L 不知道為什麼我跟隊友有極大的溝通障礙，我跟鄭忠宜對話好久，蘇柏瑄中途還一直補充東西我才搞懂，然後他們一直宣稱這是我的絕活，搞不懂什麼意思。
但多想一下就發現這可以仿造可能大二某場團練的霍夫曼 trick，就是把一樣的值壓起來做，這樣複雜度就會某種程度的很好，具體多好我也不知道，但題目 $n\leq 20$ 感覺就是很好。
等到蘇柏瑄寫完 C 之後，他本地測範測輸出一個無限大，我們兩個相繼檢查 KM 都覺得板子沒抄錯，所以應該是他模建爛了，但因為我不知道他在幹嘛，所以他一開始問「如果無解會怎樣？」的時候我的第一反應是「KM 又不會無解」。不過仔細想想就知道當下他在問他丟進去的模型無解會怎樣，而答案就是會加進無限大的邊權，可惜我當下反應太慢沒想到，浪費了一小段時間我們才想通其實就是蘇柏瑄模建爛了。
--pC AC 0/76
然後就換我上來寫 L，2014 明明就難得要命，怎麼 2015 已經開了四題還在水題區（雖然已經過一小時以上了，但感覺就是題目太長在拖時間）。
L 也挺好寫的，寫一寫抓一些白痴 bug 就過了
--pL AC 0/91
不過中途其實被蘇柏瑄打斷去驗 E 的解，這乍聽之下跟我剛剛在閒暇之間想的第一方向是吻合的，所以我本來想很快同意，但蘇柏瑄還是想跟我講清楚一些細節，我就聽他講完。
聽上去完全沒有問題，所以 L 寫完之後就換他上來寫 E 了。
不過有趣的是 E 現在只有一隊開掉，下一題比較像是 I 或 J，但反正我們會 E。
我下機後就聽 icube 講 J 的題目，一開始他給了我一個感覺超級難做的版本，我看了題本上的圖片之後就質疑他這個真的是「四邊形」嗎？感覺像是「平行四邊形」。
而他多看一點之後就發現好像真的是這樣，我們就把式子重寫一遍，發現一切都變超級簡單，最後就是一個卷積，但答案可以很大，所以用 NTT 就要做兩次，但自從之前團練用過人生第一次的賽中 FFT 後我就開始信任 FFT 了，看他答案雖然大但也不會多大我就準備等蘇柏瑄下來開抄 FFT。
等到蘇柏瑄過了 E 之後
--pE AC 0/107
我就上去開始寫 J，而蘇柏瑄下機處理 I。
J 其實就真的很好寫，所以沒多久我就收掉了。
--pJ AC 0/114
再來我就稍微估了一下剩下的 B、G、H、K、M 的狀況
- B 剛剛在空閒中其實有聽過，當下大概有方向了，多想一下就覺得他根本只有一種做法，反正就是切成好多段三分搜吧，找時間寫掉
- G 看起來有點物理，先跳
- H 跟鄭忠宜討論了一下後，覺得只要把兩個相鄰棍子中間的分界點式子寫出來可能就能 lagrange multipliers，也有可能就不用，反正我請他先寫式子就對了
- K 我發現我以前看過，但我以前根本就做不出來，感覺是一個神秘結論題
- M 看起來超複雜，可能先不碰
之後我就開始跟鄭忠宜唬爛說所有簡單環的 gcd 是拿出 m-n+1 個簡單環的長度 gcd，但鄭忠宜怎麼聽怎麼覺得不對，然後就畫反例給我看，我到現在還是不知道我這爛結論的記憶是哪來的。
接著蘇柏瑄就傳了 I
--pI WA
因為要放蘇柏瑄去 debug，又好像沒題做了，我就上來寫 B，開始把我要的板子抄一抄，抄到一半蘇柏瑄要改個東西他就再上來改完傳
--pI WA
我就繼續抄我的板子，後來他又改一次才過
--pI AC 2/139
這時候我看 M 被開掉了，而且蘇柏瑄說是很底下的隊伍，就讓他去看，但這裡我犯了一個致命錯誤，就是我完全沒有跟隊友討論過 B 的任何細節。
現在想想這個時間點應該就是最佳時機，他應該能大大縮短我 B 後期鬼打牆的時間，讓我們能多過至少一題。
總之蘇柏瑄就乖乖看完 M 之後說這只是一個模擬題，給做不出題目的隊伍做的，我就說好那他慢慢想，我繼續寫 B，鄭忠宜在旁邊同時想 H 跟 K，G 可能被我們忘了。
大概沈寂了一陣子之後 B 寫完了，但本地出事，我印了東西沒看出來就先讓蘇柏瑄寫點東西，我在旁邊畫圖看，後來找到問題後我看一看雖然覺得沒問題，但仔細一看輸出，跟範測有 3e-5 的精度誤差，這其實非常詭異，我當下其實有提出來說我覺得這不對，因為值域一大、答案依然小的話，相對誤差就還是會大，1e-3 的相對誤差估起來是撐不過去的。
這裡應該是第二個致命錯誤，我應該更詳細的在這裡把我的作法說一遍，隊友可能就會猜到問題在哪了（
但我沒有，跟蘇柏瑄嘴砲一下之後我就選擇上傳（還因為我們 WA 過沒首 WA 壓力）
--pB WA
果不其然直接吃 WA
在一旁看 code 一陣子我就發現我 x, y 互換的時候向量沒跟著換，智障，改完傳
--pB WA
後來又抓到我有 i, j 打錯，有夠白痴，改完再傳
--pB WA
到這裡我覺得我真的是不知道為什麼心急了，這兩個 bug 都是好好檢查會抓到的，怎麼就先傳了呢。
我開始在旁邊好好想清楚，沒一下子我就想到算兩個凸多邊形有交集怎麼可以只驗 point in convex，我可能幾年前就自己想到過了，現在忘記是什麼白痴（
趕緊在蘇柏瑄想事情時馬上上來補驗線段相交，改完再傳
--pB WA
有夠可悲。
這時候我在紙上多畫了幾張圖，再盯盯自己的 code，不對啊，啊兩個線段平行我是怎麼求交點的？
我馬上又發現我漏了這個 case，到底是怎樣QQ
感覺自己真的是急了，不知道在急什麼，其實我們在 I 之前的成績都不能說差，可能是手速場步調太快，而我們本來就不算是手速隊伍，所以前期在有點後面就慌了？
改完之後這次真的再多想了一下才傳
--pB WA
投降。
這次我在旁邊真的想不到問題了，在蘇柏瑄寫完 M 之前我就開始在跟鄭忠宜討論 H，發現 lagrange multipliers 完全就不是對的方向，但從答案可以看出某種神秘比例關係，我就開始懷疑是需要一些通靈，而且 JAW 過了，感覺就需要一些數學直覺。
後來我甚至開始在唬爛搞不好可以用柯西不等式做他，但我可能就是瘋了，多想一下就發現又不是每一項都是自由變數（
渾渾噩噩到了蘇柏瑄把 M 寫完，還 debug 了好一陣子才搞定，上傳
--pM 0/256
我就半放棄的說我要來亂試 B 了，結果我一坐到電腦前就想到，如果三分搜的谷底是水平線，那我真的會都算到一樣的值嗎？
恍然大悟之後我趕緊調整一下取答案的方式，並放寬 eps 之後重測範測，果然答案開始能逐漸往範例輸出靠近了，但怎麼調 eps 都調不成範測，我就抓了一個最接近範測的 eps 一傳
--pB WA
這時雖然是非法資訊，但我們改 WA 了比之前後面很多的測資。
因為不小心知道這是有效改進了，就將就的接受了這件事，而我覺得這題真的不能再拖了，
就跟隊友說我要調 eps 爆傳了。不過我心中其實是覺得這個 eps 調了應該不太會有差就是（
就跟隊友說我要調 eps 爆傳了。不過我心中其實是覺得這個 eps 調了應該不太會有差就是（
果然，調了幾次之後
--pB WA
--pB WA
--pB WA
結果都沒有變，我就冷靜下來多想我到底錯了什麼。而就是這麼突然，我馬上發現了我漏的最後一個 case，那就是在一開始如果沒有接觸的話，交集面積雖然是 0，但不可以算進答案，可是我會算進去OAO
趕緊把之前特判的凸多邊形交集拉到外面之後改一改上傳
--pB WA
怎麼會，我以為這已經是最後一個 bug 了...
但我還是姑且測了一下剛剛想到的 case（我其實現在沒有很懂為什麼當時不是先測再傳），一測就發現我根本沒改好，正式修好之後再傳
--pB AC 10/273
以一個淒慘的 penalty 通過了。
雖然我們 penalty 真的蠻慘的，但仔細看計分板好像也沒輸太多，認真說就是剛剛 B 的敗筆太多了。
不過比賽還沒結束，我聽了 G 之後覺得不可能做完，就趕緊看看 H 怎麼做，因為怎麼想都是這題了，如果真的是通靈結論題就還有寫完的機會，所以就三個人都砸進這題。
蘇柏瑄跟鄭忠宜在討論他們自己的方向，我在旁邊嘗試認真的列好式子分析，到賽末五分鐘時他們兩個突然在討論聽起來正確的東西，我湊過去一聽到「遞迴」兩字我就突然一切都懂了，
什麼數學題，就是假的，完全被自己一開始的直覺騙了。
什麼數學題，就是假的，完全被自己一開始的直覺騙了。
因為不可能寫完，所以我們就結束了。
結語
1. 賽後鄭忠宜默默的在把 H 寫完，在 40 分鐘後獲得 AC，感覺如果前面沒雷的話這題就是我寫，然後細節就可以由隊友平行想得更清楚，應該能更快寫完，真是可惜。
2. 不過這次的大敗筆還是 B，主因應該在我身上，在這篇文撰寫的當日我嘗試單刷了一場 ICPC 也再次注意到我單個人時是很容易掉細節的，之後應該要硬著頭皮多跟隊友確認想法。
3. G 也被 JAW 過了，我到現在還是沒有很了解這題，也不太清楚為什麼他會被丟掉，感覺好像不太合格，應該半場有空要了解一下才對。
4. K 沒時間想，好可惜QQ 因為雷掉的主因是 B 直接沒得檢討。
5. 怎麼 2015 就銀了，好可怕。
6. tourist 是妖怪。
8BQube 加油！
留言
張貼留言