【World Finals 團練紀錄】2019 ICPC World Finals

 

簡介

The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。

隊伍組成

National Taiwan University, Team 8BQube

蔡旻諺（baluteshih）

蘇柏瑄（briansu）

鄭忠宜（icube）

不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷

前言

因為 2018 要留到之後跟 ckiseki 一起打，就先跳過。

但這場後期真的是有點爆了，啊不就幸好前期夠穩（

目標：打出一場沒有遺憾的 World Finals！

成果

時間：2023/9/11 13:25~18:25

$\color{green}{A}$ $\color{red}B$ $\color{gray}C$ $\color{green}D$ $\color{green}E$ $\color{gray}F$ $\color{green}G$ $\color{green}H$ $\color{green}I$ $\color{green}J$ $\color{gray}K$

Penalty：745

Rank(versus official)：7

題目

https://icpc.global/worldfinals/problems/2019-ICPC-World-Finals/icpc2019.pdf

比賽過程（省略題目敘述）

開場是沉默的讀題目環節，一陣子了也不見有人開出題，我第一個看的題是 E，但我看了一陣子都沒完全看懂，就請蘇柏瑄讀完他的題之後幫忙看，聽完之後果然是水題，但看起來需要 BCC，我就先開抄，而蘇柏瑄也說他會 A，我就說那我抄完板子（或甚至我還沒抄完也可以打斷）他 OK 了就他先寫，因為我覺得我有細節要想。

抄完之後一下子他就接手了，我在旁邊想 E 怎麼好好寫，邊想就邊發現 E 真的先被開掉了，果然是水題。

因為 E 處理子樹是不是樹實在是太麻煩，整個連通塊是樹的 case 可以特判......咦，那不是樹只要一直拔葉子就好吧？這個作法太乾淨了，我就在蘇柏瑄的中途小空檔簡單跟蘇柏瑄講了一下我想幹嘛，他同意之後我就開始想細節。

想完細節之後蘇柏瑄還沒好，鄭忠宜就跟我講 H，聽完之後就直接冒出可以用倍增輕鬆做掉的想法，我另外問了一下找環（又是一題環）的部分可不可以更好寫，但還沒想到蘇柏瑄就過了 A

--pA AC 0/27

我就上去寫 E，跟鄭忠宜說他如果想到再告訴我。

邊寫 E 我邊發現前面的圓方樹都白抄了，現在這個作法根本用不到，但我想說寫了都寫了就留著，這個決定蠻笨的，等等就知道為什麼了。

寫到一半蘇柏瑄問我環形上判每個點當開頭能不能括弧匹配是不是怎樣怎樣判就可以了，聽起來超級對，他就說他等等可以寫 D。

因為 E 真的超好寫，所以一下就寫完了，結果傳上去

--pE RE

RE！？怎麼會（

多看了一下感受不到問題，但找不到可以 RE 的點，只有可能是板子的部分搞爛了（但板子是完全不需要的，可以直接拔掉），我就跟隊友講這件事，討論一下之後就覺得拔了板子再傳一次。

--pE AC 1/44

好笨，早知道一開始就拔了（

但板子怎麼會錯，晚點再來找原因OAO

接著就換蘇柏瑄寫 D，我回去問鄭忠宜 H 有沒有更好寫的寫法，他說沒有，所以我就先在腦中想了實作 H 的細節後繼續看其他題。

鄭忠宜一連跟我講了 G 跟 J，G 是 AC 自動機裸題，感覺完全沒有難度；J 應該可以做，方向上大概也知道要幹嘛，只是就要想想哪條路才會走到正確的複雜度。

但沒多久蘇柏瑄的 D 也寫完了，一傳

--pD RE

蛤怎麼又 RE（

而且雖然作弊，但 CF 說是範測就 RE 了，雷XD

但反正我就先上來寫 H，寫沒多久蘇柏瑄就找到他有一個迴圈小 n 打成大 N，一個代表 n 最大值的 const int，白痴(X

--pD AC 1/61

再來就是我開始飆 H，蘇柏瑄看了看題目就說他肯定要寫 I，他是 parser 題，甚至底下有人過了應該就是沒料的題，所以他先開始讀了。

H 用倍增超級好寫，沒多久我就打完了，傳上去

--pH AC 0/67

直接一發開掉，然後接下來就是緊接著 G。

G 也是寫很快，但寫完之後範測不知道錯什麼，我就找了好久，最後才發現輸入字串要 reverse，好笨。傳上去

--pG TLE

蛤？TLE？不是線性嗎？

我甚至已經知道在樹上走時不可以每次暴力跳 fail 所以先建好 fail 會掉到哪了欸。

因為找不到問題就讓蘇柏瑄上來先寫點 I，我跟鄭忠宜在旁邊討論問題，但就感覺沒有問題，所以我就先聽聽 J，因為鄭忠宜說他做完了。

J 最麻煩的就是要算直線交點來得出區間，我實在是很討厭這個，就請鄭忠宜導交點式子，我有了那個式子之後後面應該就好寫了。

因為蘇柏瑄隨時都可以打斷，我就開寫 J 了，邊寫邊偶爾討論一下 D 的問題，然後我就突然開始懷疑我建好 fail 表的方式不是正確的，但我記得我上次在 ARC 這樣建沒 TLE，還是 WF 測資真的太強了（

我就回去改了一下，改成每個點會直接讀自己 fail 的資訊來明確的 O(sigma) 建表，一傳

--pG AC 1/108

還真的 OAO

我學會了，WF 果然會教育人。

到這裡我們的名次看起來都不錯，雖然吃了一些 penalty 但速度算快的，狀態頗佳。

接下來就是寫 J 的時間，得到式子之後一切都很明朗，不過寫完還是錯了範測，改幾次之後就好了，看一看也沒啥問題就傳

--pJ AC 0/138

好欸，這時候 6 題看起來很棒。

接著就讓蘇柏瑄繼續肝他的 I，我看了看計分板

- pB 看起來可以做，有人過了

- pC 沒人開，鄭忠宜一直在說他是不是模擬就好了，但我沒去關心

- pF 鄭忠宜說我未卜先知感覺就是梯形剖分掃描線，不是啊我一直在喊說要帶這個板子但還是沒帶，所以就很失敗，這題大概只能擺後期了

- pI 蘇柏瑄會開掉

- pK 不知道是啥，也不知道為什麼沒看（

看起來下一題就是 B，鄭忠宜也有想過一點內容了，討論一下雖然感覺很危但大概就是 n^2logn，log 是二分搜。

只是二分搜的部分看起來是要搜 U 型函數某個水面下的區間位置，這感覺超難搞，我就在旁邊努力把式子寫好，感覺沒問題之後就先上去寫。

但明明我式子寫好了，寫的過程還是很痛苦，主要是有各種邊界 case 搞不太定，弄了一陣子之後寫完一測錯成智障，就一直在 debug，蘇柏瑄繼續抓空擋寫 I。

bug 越抓越浮躁，然後我就突然以為這題性質很好，可能我要搜的東西是一個後綴，我就很開心的改成只搜後綴，雖然還是修了一陣子但範測過了，就傳

--pB WA 

然後就吃了大大的 WA，而且一不注意就快封版了，什麼鬼，這題好痛苦。

過一下下蘇柏瑄的 I 就好了，一傳

--pI AC 0/240

是很開心的一發，然後他就去跟鄭忠宜討論 K，我在電腦前對著 B 不知道怎麼辦，只好寫對拍，拍一拍就抓到後綴的性質是爛的，然後我就突然整題都不會了，完全不知道怎麼修好。

大概剩 40 多分鐘的時候我就開始在喊我不會做了，不過還是硬著頭皮修，剩半小時的時候蘇柏瑄進來一起討論，但可能是我很躁的關係，我們的討論速度超級慢，我腦中會一直想著時間不多了可能不該討論（我認為）不必要的東西，就一直在說什麼不重要，實際上可能在拖慢討論速度。

看似還有很多時間，但我就是完全不知道怎麼辦，這最後一小時我們就什麼都沒做，結束了。

結語

1. B 真的不知道怎麼好好寫欸，不知道要怎麼學會好好寫這種題目（

2. 可能有另一個問題是我寫到很躁，我其實在賽中也有注意到，甚至碎念一句「我覺得我現在很躁但我不知道怎麼處理」，我現在還是不知道，怎麼辦（

3. 這場敗筆大概完全就是這題，應該沒什麼好說的了，前期非常好。

4. E RE 的問題是我在板子有該乘 2 的地方沒乘 2，就是抄錯了，但真的該把不必要的東西刪一刪。

5. 沒時間想其他題好可惜，現在想想 B 最正確的做法可能是直接及早丟給蘇柏瑄請他重想一遍，剩半小時他才進來直接來不及。

8BQube 加油！