【World Finals 團練紀錄】2020 ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
為了感受一下近代 World Finals 的感覺，就挑了相對價值比較低的三機場試試水溫（不過我們用一機挑戰），順便趕在蘇柏瑄被抓進去前也比較有感。不過這場打起來真的有夠白痴，詳細就交給紀錄了。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/4/7 13:42~18:42
$\color{green}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{green}E$ $\color{green}F$ $\color{green}G$ $\color{gray}H$ $\color{green}I$ $\color{green}J$ $\color{gray}K$ $\color{gray}L$ $\color{green}M$ $\color{gray}N$ $\color{green}O$
Penalty：2410
Rank(versus official)：8
題目
比賽過程（省略題目敘述）
開場設好環境之後我就有點感受到我有點緊張，不太清楚在緊張什麼東西的，我拿了題目比較短的 G 後還沒看完幾句鄭忠宜就問了「我們打 Finals 的方針是什麼？我看到能做的題應該要先講嗎？」
確實應該好好想一下遇到這種狀況怎麼處理，到時候在結語那邊再下結論。
但反正我當下就說好啊可以先做掉看看，就被丟了 O，聽完題之後確實差不多做完了，
但我多找到了一個需要額外判循環節的 case，確定看起來沒什麼大問題，也還沒有其他人有題要做我就先寫了。
但我多找到了一個需要額外判循環節的 case，確定看起來沒什麼大問題，也還沒有其他人有題要做我就先寫了。
寫到一半 G 被開掉了，於是就請鄭忠宜快去看，但過一陣子又逐漸有 C, D, E 被開掉，步調可以說是真的非常快，不愧是三機場。
在我寫完之前蘇柏瑄就表示 E 是水題了，然後他說 C 是半平面交，但那個開題速度讓我有點難以相信，D 他則是說不太會。然後鄭忠宜表示 G 可能要寫比較久，N 看起來一臉 gradient descent。
不管怎麼樣，我寫完 O 之後測完並手動測了幾筆之後傳
--pO WA
開場就首 WA，讚喔。
換蘇柏瑄上來寫 E，他寫到一半我就發現我耍笨打錯東西，再傳
--pO WA
劇慘，開場 WA 兩次。而看見這個結果時蘇柏瑄也差不多寫完 E 了，一傳
--pE WA
莫名其妙，開場 WA 三發，這個數字還會上升嗎（
不過蘇柏瑄馬上就發現他在大耍笨，E 的輸出是每個數字換行他寫成全部一行，我當下問號，
這個對範測真的不會發現嗎。
這個對範測真的不會發現嗎。
--pE AC 1/40
然後一旁在幫我看 code 的鄭忠宜就問我 minimum rotation 完之後有比兩個一樣嗎，還真的沒有，這什麼低級錯誤⋯⋯，但
--pO WA
持續吃 WA，沒多久鄭忠宜又斥罵我說在寫什麼東西，if (db != db) 到底是什麼爛，一改再傳
--pO WA
到這裡我已經不知道自己在幹嘛，有點 WA 到沒什麼緊張感了，總之就是一個非常破的開場，看起來還真像是三機因為失去待機思考時間就爆傳。
不過這次我是真找不到 bug 了，蘇柏瑄表示他希望一起進來加入 debug 的行列就在嘗試幫我生測資，但我想到的是我應該要丟掉這題才是上策，就直接丟掉去寫蘇柏瑄宣稱是半平面交的 C。
這個過程都沒測出 bug，蘇柏瑄除了幫我找問題之外還有同時在想 A 跟 D，等到我刻完 C 之後再傳
--pC WA
真是太好了，我還沒 AC 過任何題目。
因為真的是 WA 的亂七八糟，而且計分板看起來已經把題目開到不知道哪裡去了，我們三個都有點小愣住，不過可不能三個人都這樣被這兩題卡住，我們這時看到計分板上的 D 開得異常的多，而 G 看起來也不少，我們就開始逐漸轉移焦點。
首先蘇柏瑄表示他想猜 D 直接 greedy 折就會過，這時因為我們 penalty 已經夠高了，先早點猜一題也不虧，就決定讓他上去寫，但沒多久鄭忠宜就抓到我 C 沒判 n=1，加完傳
--pC WA
哈哈還是 WA，我只好去上廁所想 G，結果還沒走到廁所就差不多做完了。我走回來之後確認了 G 的範圍看起來 CDQ 兩個 $\log$ 是沒問題的，鄭忠宜也表示他是一樣的作法，而且怎麼想這題就都是這樣做。
等到蘇柏瑄就寫完 D 後，一傳
--pD AC 0/113
終於又多一題，雖然還是很可悲的只有兩題。
因為 O 跟 C 還是沒有進展，而我們手上有我熟悉的 CDQ 和蘇柏瑄說他大概寫完 case 的 A，因為他相對沒有把握就決定先讓我上來寫 CDQ，基本上這個 CDQ 因為一點變形都沒有就很順的刻完，不過再改一下即使過範測後還是多檢查了一下，果然抓到有地方 bit 沒重設，好可怕，加了之後再瀏覽一遍上傳
--pG AC 0/133
好耶，第一題 AC 是在兩小時後。
接著就換蘇柏瑄上來刻 A，我看了看計分板，下一題看起來要嘛是 M 要嘛是 J，我跟鄭忠宜就分別讀這兩題，我看完 M 之後第一瞬間只是記下了題目還沒思考，就先聽鄭忠宜講 J，但聽完之後我就說不就是在樹上把奇點配一配而已嗎，這明顯就是一個蘇柏瑄題，就把 J 放到他前面。
接著我就跟鄭忠宜講 M，講完之後他說那我們先討論 b 不是 2 跟 5 的倍數的 case，但我跟他說我有另一個想法，問他有沒有聽過同餘最短路，我稍微講了一下這東西的概念之後我就邊講邊在腦海裡把這題做完了。很順的把 M 的做法講完之後我看了一下計分板，吃 penalty 的人有點多，我就問說這題有什麼陷阱，過一下子鄭忠宜就發現 d = 0 的時候要特判不可以有前導零，
聽起來非常有道理。
聽起來非常有道理。
接著蘇柏瑄的 A 就 WA 了範測，換我上去刻 M，M 老實說真的非常好寫所以中途沒什麼障礙，不過蘇柏瑄還是先找到了他的問題，他確認之後一傳
--pA WA
結果換他進入了 WA 地獄。
在蘇柏瑄在一旁 debug 的同時，我 M 寫完抓了幾個問題就過了範測，自己多測幾筆也沒問題，就上傳
--pM AC 0/170
信心有在慢慢回來，還有題目在 pending，想辦法靠題數追回來就對了。
下一題看起來比較有機會的是 F，但在那之前鄭忠宜提議要不要先對拍 O 看看，畢竟那題可以自己產 Same 的測資檢查我是不是都會輸出 Same，我同意之後就說等蘇柏瑄改完他的東西我就開寫。
過一下子蘇柏瑄就改完他找到的問題一傳
--pA WA
然而還是沒過，只好換我上來寫對拍。
對拍寫完還真沒找到問題，所以我只好把座位讓給蘇柏瑄開始跟鄭忠宜討論 F，但 F 我一聽完就覺得他只是個旋轉掃描線裸題，我問他說真的有可能得兩個點卡在不同側的直線上嗎，他也沒辦法反駁我，我就去廁所想一下。
回來之後鄭忠宜就嗆我說對拍用的 python 在亂寫，他改了一下一測就直接抓到問題，我們趕緊多看一下發現是我對浮點數太有信心了，輸入浮點數轉整數肯定是要 round 的啊⋯⋯真的是學到教訓，我之前還幫資芽學員抓這個 bug 耶（
改完上傳
--pO AC 4/196
終於有一題噩夢在這裡被解決了。
沒多久一旁蘇柏瑄突然開始笑，他發現他 A 裡面的曼哈頓距離在亂打，減號打成加號，好喔。
但改完之後還沒完，他自己一測還發現會莫名 RE，而且是在輸入數字足夠大時才會發生，但我們明明就有開 sanitizer，所以感覺也不是 overflow，但不管如何他還是先把 int 改成 long long ，結果一測還真的沒問題了，C++ 在偷搞事吧（
一傳
--pA AC 2/203
終於也過了，這時我趕緊跟蘇柏瑄講 J 要幹嘛，並同時請他幫我驗一下 F 是不是真的不需要考慮兩個點卡在不同側的直線上，他想一下也覺得聽起來很對，我就開寫了。
F 的做法對在 IOIC 講計算幾何的我來說完全是輕鬆，甚至可以全整數做事，所以刻完之後⋯⋯沒有，錯了範測。但因為範測錯得離譜我就沒有讓出電腦，反正 J 的樹 DP 本來就可以讓蘇柏瑄再多想一下，抓到問題之後過了範測檢查一下就傳
--pF AC 0/222
我當下就直接嘴砲說 2020 的人怎麼這麼笨，但去上完廁所之後想一想搞不好只是大家不習慣寫全整的東西所以被卡精度，但隨便。我還順便發現這場比賽真的是水題一堆，寫到這裡感覺沒還沒有什麼思考成分，濤哥當初說的要先寫完九題才能開始比賽是對的。
接著我就在旁邊盯著我的 C，然後蘇柏瑄繼續寫他的 J，等他寫完錯範測後，我提議說要不要乾脆來唬爛看看是精度問題把 double 改成 long double，結果一傳不得了，跑得稍微久了一些，但蘇柏瑄也抓完他的問題了就讓他先傳
--pJ AC 0/236
在他嚷嚷著 J 簡單啦的同時我開始著手把 long double 再改成 __float128，改完之後傳
--pC AC 4/242
終於到了九題，我們可以開始比賽了（？
而蘇柏瑄馬上就表示他其實偷偷快會 B 了，我就先聽 I 的題目，鄭忠宜跟我講完之後我就去上廁所，蘇柏瑄跟鄭忠宜確認 B 的想法。
我回來之後蘇柏瑄已經開刻，然後我開始跟鄭忠宜順 I 的想法，講一講我就問他說是不是其實對 e_i := 做每個任務前讓他 c 倍最大可能的經驗值量 排序就做完了，他一時覺得我很聰明就被我說服，我就問蘇柏瑄說他還要多久，他說應該快寫完了，我就慢慢等他⋯⋯錯範測。我們還在想要不要再挑戰多開一題，當時鄭忠宜是說必須我們兩個都刻很順才有可能。
於是就換我上來刻 I，因為真的沒什麼需要寫的就寫完然後⋯⋯錯範測。我開始說笑死果然不順。
接著我跟蘇柏瑄就交互 debug，蘇柏瑄接連找到了兩三個問題，每一次他都說「喔這 icube 剛剛跟我講過了但我忘了」，不知道在幹嘛XD
我則是發現我好像 claim 錯了，對 e_i 排序是錯的，跟鄭忠宜講完之後就陷入尷尬狀態，但我相信這應該是對另一種東西排序就想找線索。
等到蘇柏瑄終於抓完他的 bug 一傳
--pB AC 0/278
我就跟蘇柏瑄講了一遍現在 I 的問題是什麼，他聽完之後也一起進來幫忙想，這時候比賽剩不到 20 分鐘，看來是勢必得把剩下的時間拿來押這題了。
互相嘴砲一陣子之後，蘇柏瑄突然說不如我們倒著想，接著我就寫出了 S - x_i <= e_i 這種東西，老實說這時候我有點小混亂，但我選擇把「那是不是對 e_i + x_i 排序啊」直接說出口交給隊友判斷，蘇柏瑄簡單想一下就說「好像很對，不然你先寫」，我也覺得不然就先寫趕緊開始改。
這時候比賽大概剩 7 分鐘，我火速改完之後就過範測，隊友趕緊催促我傳
--pI RE
居然不是 WA 是 RE，我馬上就發現是我範圍開太小，跟大家道歉之後改完傳
--pI RE
因為剩 5 分鐘能做的不多，但 RE 肯定是還有什麼白痴東西在搞，而且我們 penalty 已經夠大不可能有用了，我就把範圍隨便改大再傳
--pI ???
不對，在我傳完的當下我就發現是我 e_i 會很大所以會跑超出範圍，我趕緊開始改，改完之後傳
，而在結果改到一半鄭忠宜就突然說了一樣的東西，我說我就是改完那個傳的，接著兩筆結果出來
--pI RE
--pI AC 3/297
驚險的結束了這場 2020 WF virtual。
結語
1. 這次雖然沒有題目卡到最後沒抓完 bug，但前期真的是⋯⋯
2. 承上，結果這次 O 跟 C 我們完全是被浮點數攻擊，看來我的浮點數自信還很半吊子，除了 O 的 round 欠檢討之外我也另外多研究了一下 C，半平面交的判斷是會讓值域噴到 C^5 的，所以題目值域 10^5 很容易就出事了。
3. 再承上，但我覺得怎麼可能會需要這麼胖的值域才能判完，肯定有辦法讓他 C^4 全整，就在晚上研究了一陣子之後通靈出了一個方法，目前看起來運作得很順利，我也藉機把半平面交的 code 壓短了，算是不錯的收穫（？
4. 這場比賽很遺憾的因為前期爆開沒辦法達成早點把題目看完，又得之後實行了。
5. 除了浮點數問題外，感覺我們實作穩定度還是不知道為什麼不穩，是不是該練實作一百題了。
6. 結束後鄭忠宜多花了一點時間用 graident descent 唬爛 N，但範測就被卡爛，所以他就關機把 code 消滅了。我懷疑他會被卡在 local min，不太清楚。
7. 回家的路上我跟鄭忠宜討論了一下 H，看起來是很可以唬爛看看的題目，有點可惜，如果前 11 題不要有那麼多波折能順順開的話就可以花時間在上面了吧，果然還是要穩才是上策⋯⋯之後再看看吧。
8. 開場看到能做的題目到底要不要寫呢？我覺得，沒有十足自信還是先緩緩好了（
8BQube 加油！
留言
張貼留言