【World Finals 團練紀錄】2013 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
這次講好了開場如果沒有特別有自信能開掉的題目就不要先開始寫，多看題目優先。然後最好在第二個小時就要有人看完所有題目。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/4/14 13:10~18:10
$\color{green}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{green}E$ $\color{green}F$ $\color{gray}G$ $\color{green}H$ $\color{green}I$ $\color{green}J$ $\color{red}K$
Penalty：1089
Rank(versus official)：2
題目
比賽過程（省略題目敘述）
開場我老樣子設環境，打完之後就下來一起讀題目，一開始我看完 D 覺得應該不難，但畢竟沒有把所有細節秒完，遵循原則我就繼續往後看，接著依序看到看起來超噁的 G 以及看得沒有很懂的 H，結果看到 J 覺得有點像板子題，鄭忠宜就跟我說那是裸的圓交集多邊形面積，因為我們有板子，雖然感覺跟以前的人比這好像是犯規，但誰管他啊(X
我開刻的同時隊友們繼續讀其他題目，刻到一半 F 就被開掉了，請蘇柏瑄去處理之後他表示那是水題，但我也差不多結束了，這時候寫完測幾筆一傳
--pJ AC 0/14
貌似是整個計分板首殺(X
接下來就換蘇柏瑄上來寫 F，幾分鐘後 D 就被開掉了，我稍微去把式子寫了下來，發現事情沒有我想得那麼簡單，在蘇柏瑄 debug 的空檔我稍微借用了一下測點東西也算出不理想的數字。這時我就請鄭忠宜幫我讀清楚 H 的題目，因為他看起來一臉就是很水的區間 DP 之類的題目，但我沒讀懂細節才放在那邊。
等到蘇柏瑄寫完 F 一傳
--pF AC 0/23
他是先說他可以寫 A，因為 case 都差不多了，因為我們這裡還有東西要討論就讓他先寫，不過過寫到一半他就問我說有沒有比較好判存不存在有向環的方法，我跟他說不就拓撲排序看有沒有反過來的邊，但他好像沒聽懂。
過一下子我就想到 D 因為可以對指數大到小排序之後 assign 給前幾小的質數，所以爆搜起來就會非常容易，跟鄭忠宜確認之後他說好，然後他就跟我講了 H 的題目，然後確實就是一個水題，但區間 DP 時算 cost 的方式沒有很明確。
這時蘇柏瑄開始說他判環有障礙，我就上去幫他打了一個（
等到蘇柏瑄寫完 A 想檢查的同時，我猶豫了一下要寫哪題，但很快我就決定選擇不先寫還沒把細節寫完的 H，開寫 D。
蘇柏瑄檢查得沒有很快，忘記是範測就錯還是他手生東西錯了，總之花了一點時間在旁邊 debug，然而 D 的 code 也沒很長我一下就寫完了，寫完測一測我看起來很 OK 就先傳
--pD WA
吃了這場第一個 WA，找了一下找不到 bug 就跟鄭忠宜確認一下，結果他說他其實不知道題目，剛剛我跟他確認想法他只是無腦回答我而已（Ｘ
幾分鐘之後蘇柏瑄修好他的 A，他表示他在亂編號輸入，然後一傳
--pA AC 0/57
我繼續 debug，蘇柏瑄去看有沒有其他可開的題目。我跟鄭忠宜順過一遍 D 的做法，他就問我說乘法不會 overflow 嗎，我就指給他看說我寫了乘法的 oracle 還有跟 INF 取 min，才發現乘法的部分根本沒轉型成 __int128，笑死（
--pD AC 1/61
接著我就開始寫 H，過程中蘇柏瑄說他應該會 C，他跟我確認了一些東西我回他 OK 後他就說等等要 Dinic。
H 幾乎寫完之後我測一測發現不太對勁，我得知的題目敘述跟範測對不上，就請鄭忠宜去確認意思，我直接接著幫蘇柏瑄打 Dinic，打完之後先下來讓他寫 C，我下去跟鄭忠宜討論題目敘述。
H 的題目敘述可能沒有說非常明確，但稍微釐清了一下什麼是俄羅斯娃娃之後（？），突然就好像理解了。但變成這樣我就還有東西要改，而且還得多想一下，蘇柏瑄也說他快寫完了就繼續讓他寫。
沒多久之後蘇柏瑄寫完了，多找一下問題之後傳
--pC AC 0/90
接著換我上來改 H，改完之後多確認幾下之後傳
--pH AC 0/94
到這裡開場算是順利，我們的排名也蠻前面的，也差不多是要來釐清一下這整場的局面了。
剩下的題目中，B 是感覺偏經典的賭博期望值題、E 蘇柏瑄他們表示是神秘爆搜題、G 是噁心幾何、I 鄭忠宜跟我講完之後看起來像是需要資結的東西、K 我沒看仔細，看起來像需要模擬的東西，然後鄭忠宜看過之後選擇扣著他。
在這之中 I 就已經在一陣子前被開掉了，而且這題又看起來比較像我的題目，所以理想上我就得做這題，蘇柏瑄跟我講完 B 表示了他的想法，但沒有很確定，所以就先去處理 E，鄭忠宜兩邊跑。
I 要做到 (nm)^2 當然非常簡單，而且多壓一下就有 nnmlogm，但感覺都不太好，跟鄭忠宜嘴砲一下子我沒什麼想法我就跑去廁所想，結果突然就想到了我可以用並查集維護我要的資訊，很開心的回去後我抓到時機跟鄭忠宜確認並請他幫忙導某個小式子就開始寫了。
我想到的 I 的做法非常好寫，所以我其實也寫沒多久，但寫完卻還是範測錯一坨，de 了一陣子的 bug 之後才傳
--pI WA
不是吧又吃 WA，因為一時之間找不到問題就換蘇柏瑄上來開寫 E，但沒多久我就發現我有 m 打成 n QQ
--pI AC 1/161
一不小心時間就過了一小時了（
接著我開始跟鄭忠宜確認 K 的內容，他表示他沒有很確定這題該怎麼做，但我理解題目之後怎麼想都覺得他是一個大爆搜題，怎麼可能有別種做法，跟他唬爛一下之後因為認為 B 感覺比較該開我就開始想 B 了。
多導了一下蘇柏瑄要求我算 B 的式子後，我沒有找到明顯可以化簡省精度的地方，就抓蘇柏瑄 debug 的空檔寫了打表的程式確認，不過看起來精度意外的很可以，可惜蘇柏瑄進來多算了一下東西之後覺得有點奇怪就繼續放著。
蘇柏瑄回去修 E，這時鄭忠宜便一起參與 B 的討論，但我們 argue 了一陣子，他覺得策略上不太可能設置一個輸慘的左界，使得輸到某個固定的左界就直接放棄，我一開始還有點被他說服，但多想了一下之後覺得超級怪，如果是這樣的話因為他承認有上界，那答案不是總該是整數嗎？
討論進展得沒有很順利，而且鄭忠宜還有兩邊切換，差不多時候蘇柏瑄就傳了 E
--pE WA
卡住的同時我就上去想試著多打一些 B 的資訊看能不能 work。
過一陣子蘇柏瑄改了東西又傳了 E
--pE WA
還是 WA（
但一下子後 B 的打表看起來就有點樣子了，可以算出範測的答案，而且很巧的因為我在窮舉（上界-下界）的長度，所以我意外的發現了這個窮舉是凹的，超級意外的同時就知道可以用三分搜做這題了。
因為 E 找不到 bug 我就開始寫 B 的三分搜，寫完之後果然很穩的運作了，結果測了一下大一點的測資卻出事，多想一下就猜到是三分搜值域範圍要調整，不然太偏的地方會全都是 <eps 的東西出事，正當我猶豫要不要改值域範圍時，蘇柏瑄就說那如果戳到 <eps 直接壓右界就好了，我一聽覺得很有道理，一改果然成功，確認沒問題之後就傳
--pB AC 0/246
換蘇柏瑄上來繼續找他的 bug，我開始在腦中嘗試思考 K 要怎麼寫比較好。不過蘇柏瑄還是沒找到，我就上來開始寫 K。
K 寫到一半我就發現我卡住了，因為我不會又 dfs 又 bfs 的平行爆搜東西，跟鄭忠宜求助沒多久我就突然發現這其實是一個大 dp，或講成記憶化爆搜就好（？
因為想法有點被洗掉所以我就在重想，而蘇柏瑄找到他的 bug 了，他的特判在唬爛
--pE AC 2/263
最後的時間就是我上來火速飆 K，因為 G 根本沒任何可能寫出來。
但時間真的有點少，最後我壓在剩大概三分鐘的時候寫完，範測都過不了，就結束了QQ
結語
1. K 後來我找了一個大約二十分鐘的時間就補掉了，前面雷掉不少時間，可惜啊。
2. 承上，大致上雷掉的時間我想都是實作不穩定造成的，除了我自身實作穩定度不知道為什麼掉了之外，我尤其覺得蘇柏瑄的狀態不太好，不僅是實作比平常不穩，掉 case 頻率也變高了（
3. 再承上，我懷疑可能是他的當兵壓力造成的 QAQ 希望他早點進去當完出來再練回手感（這時間點距離他進去大概剩一個多月，但還是不知道他確切什麼時候進去）
4. 這場整體比起來還算可以，大概完全只有實作上要檢討吧，越來越覺得把實作練穩才是最重要的了，雖然我們都還只打過老的 WF 場和 ICPCPCPC，不知道是不是看得不夠多才這樣認為
。但實作練穩肯定不會錯，應該要多想一下有沒有適合練實作的方法。
。但實作練穩肯定不會錯，應該要多想一下有沒有適合練實作的方法。
5. G 好噁心。
8BQube 加油！
留言
張貼留言