【World Finals 團練紀錄】2017 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
至少回到銀了，但感覺還是打得偏差（
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2023/9/7 13:35~18:35
$\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{gray}J$ $\color{gray}K$ $\color{gray}L$
Penalty：985
Rank(versus official)：8
開場蘇柏瑄就在說他可能看過 A，但一眼就知道那是一個幾何題，他姑且跟我講了一下題敘之後我就覺得應該是幾何水題，有空就會寫掉。
總之我往後翻了一下題本後，覺得 E 看起來比較舒服，然後就發現他是一個水題，雖然隔壁的蘇柏瑄又再說他看過 E，但不重要。
因為大概真的是最水的，我就直接先開寫了，無懸念 AC
--pE AC 0/9
下一題馬上被丟了 I，簡單 dfs 題，聽完鄭忠宜指示就做完了，也是無懸念 AC
--pI AC 0/14
蘇柏瑄表示他會 F 就讓他上去寫，而我繼續讀了一下題目，翻一翻看起來是 H，一個很酷的排程問題，一時沒想法就先丟著。
接著我再看到 D，看完之後覺得難以置信的水，而且相比一般的水題更不像是題目，所以覺得大概是讀錯了，可是我又找不到問題，這時候蘇柏瑄過了 F
--pF AC 0/21
我就請他幫忙看 D 的題目，我聽鄭忠宜講 C。
C 聽完之後覺得是個經典題，但一時沒想到，不過蘇柏瑄讀完 D 了，果然是我讀錯題，在紙上畫一下之後發現就是求最大面積矩形，所以不就是超大畫框設置嗎？馬上開寫
寫到一半蘇柏瑄借了一下電腦用 python 測點東西後就說他大概會 B，但要晚一點寫，他先紙上寫點東西，然後我請他有空可以看看 H，感覺他會做。
邊寫 D 就邊發現計分板上一堆人 WA，感覺有什麼陷阱，寫完之後我就跟隊友說我要寫對拍，反正超好寫，而寫完之後對拍確實一測就抓到問題，改完之後再測也沒問題就傳
--pD WA
WA！！？？對拍都沒問題了還 WA（
跟隊友講了這個狀況之後我們就嘗試把對拍的值域調大、n 調小，果不其然一陣子就拍到一個，我把測資打出來之後畫了圖就先去上個廁所，讓蘇伯軒先寫點東西，上廁所到一半就想到我的問題了，白痴。
改掉之後傳
--pD AC 1/51
到這裡看起來該開的還有 C, K，就回去討論一下，放蘇柏瑄在旁邊做事。
K 聽起來就是先蓋 AC 自動機之後亂搞，所以我就口糊了一個做法，然後發現做不下去，就一直卡住，只好切題。
然後其實蘇柏瑄這時候到底在處理 B 還是 H 我真的忘了，感覺這段時間他有跟我說他想要在 H 寫一個 n^2，然後問我是不是對的，我就跟他說聽起來蠻合理的，但他有處理掉某個 case 嗎，結果他馬上就被說服這個解沒處理掉，我們就很完美的迴避了一個假解，算是有檢討過的證明。
爾後又聽了 G 的題目，我說這根本不能做就丟了。
接下來我認真把 C 的過程想一下之後，發現如果從大枚舉到小，那每次不過是一個匹配，就念了作法給鄭忠宜聽，他也同意，我就開寫了。
寫的過程沒什麼懸念
--pC AC 0/82
接著我問還有人要做事嗎，不知道為什麼沒有（我這時候忘記蘇柏瑄好像做完 B 了，但不確定為什麼這時候沒人回答），那就是幾何登場的時候了，我就開抄幾何板子。
寫到一半鄭忠宜突然說 H 是不是小風之前出的題，一想一下好像還真的是，而且我已經在賽前做一輩子了都做不出來，但現在先專心寫幾何。
幾何我（自認為的）非常好寫，跟蘇柏瑄確認一下，他說不能單純的驗每兩個點之間的線，我就說好，反正就是每個點極角排序之後三分搜嘛，他沒有多想就說對。
但這真是個敗筆，我寫完之後範測怎麼測怎麼錯，就切給蘇柏瑄寫 B，抓了很久的 bug 才發現根本不用、甚至不能三分搜，而是他的最大值就會發生在邊界，所以驗頂點好好延長就好了。
這導致了一個大問題就是我的 code 在這時候變得非常醜，以致於範測測過之後我漏了若干個東西，但沒抓到所以傳
--pA WA
在旁邊手生一筆測資加 sanitizer 之後就抓到 overflow，想了一下發現是射線的 MAXC 乘錯地方，
改了之後傳。
改了之後傳。
--pA WA
又馬上發現 MAXC 開不夠大，改完之後傳
--pA WA
這時候我開始覺得他很有可能還會 overflow 了，就在原地猶豫了一陣子，想不清楚，不過就乾脆一點不要讓射線乘 MAXC 好了，btwangle 都抄了就應該活用。然後
--pA WA
真的想不到問題了，我就在原地自閉，等蘇柏瑄寫他的 B。自閉一陣子也沒想到問題，就去跟鄭忠宜重新討論 K，順便聽了 L 的題目，分析一下狀況
- pA 等等一定得寫出來
- pB 蘇柏瑄快寫完了
- pG 看起來不能做，但為什麼記分板看起來有人開了
- pH 因為大概認證是之前做不出來的題，看起來也沒人過，扔了
- pJ 看起來怪噁心的，沒看
- pK 肯定得做出來吧
- pL 過的人變多了，應該也得開
- pL 過的人變多了，應該也得開
這樣算下來期望上是要有 9 題，所以我得趕緊搞定 A。
過一陣子蘇柏瑄 B 搞定了，
一傳
一傳
--pB AC 0/191
蠻有趣的是 B 過的隊伍不多，但蘇柏瑄宣稱那題他看完就快做完了，厲害。
總之換我上去認真抓 A 的 bug，然後我就突然想到，自己是不是完全忘記射線可以過頂點之後繼續在多邊形內了（
不是，我可能最近才寫過兩次類似的題，怎麼這時候還會忘記，是 WF 搞人心態嗎（
趕緊改完傳
--pA WA
是怎樣......都又抓到一個 bug 了還錯 QAQ
卡住的期間隊友們好像在討論 G，然後似乎有想法了，原來完全是能做的題嗎，我整個搞錯了。
接著就換鄭忠宜上來寫點東西測試，而蘇柏瑄一起幫忙想 K，但都想不到。等他測試完看起來 OK 後蘇柏瑄就開始刻 G，我繼續在旁邊對 A 自閉或幫忙想 K。
這時我的 K 開始在唬爛一些沒用的 dp 作法，講一講鄭忠宜就說你這樣不是完全跟給定的字串無關嗎，我一聽就發現自己在耍笨，太苦了。
因為 K 沒想法，A 又沒概念錯什麼，我就開始說要不要直接重寫 A，現在的 code 太亂了，隊友也同意，總之如果等等 G 過了、A 還找不到問題就重寫。
然後 G 就過了
--pG AC 0/231
所以重寫 A，寫沒多久就寫完了，又乾淨又乾淨的，一開始在那邊三分搜真的是在大耍笨。結果一傳
--pA WA
還是錯（而且錯在同樣的地方），真的哭了。
失望的把很短的 code 打開來看，因為 code 超短我就突然注意到了板子區，發現除法那裡因爲之前改用 template 的關係，除法那裡沒有用 double 除，白癡喔（
--pA AC 6/246
超笨欸，這個 bug 如果沒發生應該在兩次前就 AC 了 QQ。
剩不到一小時，原本理想上要開掉的 KL 都沒什麼想法，其他題肯定是要丟了，也不知道接下來的時間夠不夠兩題，但既然 K 想這麼久了都沒想法就想想 L。
我再次確認 L 的題目之後才發現原來是單獨分別對左上角跟右下角 shuffle， 不是全部喇在一起 shuffle，感覺喪失了很多性質 Orz。
但想沒多久隊友就開始提出 K 的一些方向，我就被帶過來，討論一下我們就想到如果 n=長度 +1，那其實就是在比誰會 fail 到自己身上的位置最多，往這個方向想搞不好就是對 fail 的差做統計之後排序比對，並對 n-m 截斷之類的。
不過怎麼想都覺得這還是錯的，我們就卡住一段時間，後來時間所剩不多了，我就提議先傳，反正多一題是一題，沒多也不會怎樣
--pK WA
果然錯了，但想一陣子還是沒想法，就亂改再傳
--pK WA
再唬爛另一個創新想法
--pK WA
錯得更前面了，但也只剩一分鐘，所以再亂搞一下
--pK WA
然後就結束了，慘。
結語
1. 雖然可能壓線銀，但今天的表現應該是完全不合格。
2. A 應該是第一個敗筆，只能說一開始在那邊三分搜就壞了整題，要不是我們想那樣做，A 的 code 會短很多，也會更早發現 bug，跟蘇柏瑄討論後他也覺得當初應該多想一下後阻止我而不是放我去寫。
3. K 看了解之後發現是另一個方向的猜猜樂，題解也說這非常難證明，這種題就非常不 match 我們，不過至少最後在那邊亂傳的策略算是正確的，猜中了就是有。
4. L 感覺完全要是做得出來的題，好可惜沒時間去想，A 在搞（
5. H 真的滅台，超可怕，題解直接兩頁，結束後就跑去跟小風說他隨手出了 WF 題，塗大大也說他沒印象原來這是同一題。
6. 其實認真想想問題只發生在 A 一開始果斷三分搜而已，要解決這個問題就是專心聽隊友講話，看似是大失誤，但其實是小失誤放大後的成果，所以我想未來朝這個方向加強應該可以更好。
8BQube 加油！
留言
張貼留言