【World Finals 團練紀錄】2018 ACM-ICPC World Finals
簡介
The ICPC International Collegiate Programming Contest，是由大學生參與的演算法程式設計競賽。以三個人為一組代表大學參賽，解決現實中存在的問題，培養團隊合作、創造力、創新以及在充滿壓力的環境下實作的能力。透過訓練和比賽，團隊間互相挑戰以提高可能性。是世界上歷史最悠久、規模最大、最負盛名的程式競賽。
隊伍組成
National Taiwan University, Team 8BQube
蔡旻諺（baluteshih）
蘇柏瑄（briansu）
鄭忠宜（icube）
不推薦未來有志向比 ICPC World Finals 的選手們繼續往下瀏覽這篇文章，以防暴雷
前言
差，但就這樣吧，只能期望正式賽沒有寫出 bug 了。
目標：打出一場沒有遺憾的 World Finals！
成果
時間：2024/4/7 10:45~15:45
$\color{green}{A}$ $\color{green}B$ $\color{red}C$ $\color{gray}D$ $\color{red}E$ $\color{green}F$ $\color{green}G$ $\color{green}H$ $\color{green}I$ $\color{gray}J$ $\color{green}K$
Penalty：922
Rank(versus official)：7
（前情提要）前一天晚上全面讓 codebook 增加了 code hash
開場我打完 default code 之後我就看到 F，看起來是水題，草草跟某個隊友講完之後我就開始寫了，此時一旁的蘇柏瑄說他會 B 等等可以寫、鄭忠宜說 K 是應該可以做的構造。
寫 F 到一半鄭忠宜就說他看完 G 後面的所有題目了，效率。
結果我寫完 F 之後範測沒過，才發現我有點假解少窮舉很多東西，一時修不好就先讓蘇柏瑄上來寫 B。
但 F 只是我偷懶用 O(長度) 驗寬度而已，我跟鄭忠宜講了一下其實好好用 O(空格數)=O(n) 驗就可以了，時限 12 秒感覺就是要讓我過，就打算等蘇柏瑄寫完上去改。同時我們還討論了一下 K，因為總和是 2n-2 的 degree sequence 肯定可以構出樹，所以就有 naive dp 做法，雖然兩秒但大概跑很快吧，就決定等等寫寫看這個作法。
在蘇柏瑄繼續寫 B 的同時鄭忠宜繼續跟我講 G 跟 H，G 就是白痴 voronoi diagram 亂做很水，H 感覺不太能做，但沒多久就看到計分板有人過了，扯，只是還是沒想法就決定不要被帶走專心先想好 F 跟 K 的細節。
等蘇柏瑄寫完 B 一傳
--pB AC 0/33
我就上去改 F，改一陣子就好了，傳
--pF AC 0/41
然後蘇柏瑄就表示他可以寫 A，而且很快，所以他就先寫。
我繼續聽了 C 跟 D 的題目，C 感覺不太能做，D 就是數數但輸出期望值，真可惡。
等蘇柏瑄寫完 A 之後他就先切螢幕給我寫 K，他在一旁檢查，檢查一陣子他就說好像誤刪了某個東西，改完沒多久後就傳
--pA WA
結果改了還是 WA OAO
他看了一陣子就發現輸入會爆 int 但他沒注意到，一邊抱怨題目這樣沒意義的出幹嘛一邊改完之後再傳
--pA WA
正當他還在困惑怎麼又 WA 時，一看上傳上去的檔案發現 A 根本改完沒存到檔，白痴（
--pA AC 2/66
這個問題蠻可怕的，因為 WF domjudge 上面大概看不到 code，不過我們最慘一 WA 就印的話應該還是看得出來、或看 vim 左下角的 + 好就可以了。
後來我的 K 也寫好上傳過了
--pK AC 0/75
再來因為沒什麼題做，我就打算先跟蘇柏瑄講 H 然後開始狂飆 G，講到一半我就感受到 H 搞不好答案很小，就讓蘇柏瑄幫我寫，然後我就開始寫 G。
過一陣子蘇柏瑄就表示 H 答案小於等於 2 所以是白痴，但他可以先想細節，我就不管繼續飆 G。
結果 G 先寫完了，但我錯範測，所以蘇柏瑄先讓我 debug，我想了一下發現好像掉 case 就下去跟鄭忠宜討論要怎麼補，先讓蘇柏瑄寫 H。想好後就上去補然後補完過範測上傳
--pG WA
然後發現我有地方除法忘記轉 double。
--pG WA
這下我找不到問題了（
打到這裡步調雖然慢了一些，但我覺得還算是可以救的範圍，感覺接下來才是真正失誤的點。
我盯了很久的 G 之後蘇柏瑄也寫完 H 然後上傳。
--pH WA
然後他就也跟著不知道錯什麼。
這時候我們就兩個人在卡，而 I 看起來是蘇柏瑄等等要寫的純 parsing 難度題，但因為兩個卡 bug 就被停住。
抓一陣子我才發現我 G 還有一個地方忘記宣告 double type 的函式所以被轉成整數，趕緊補上去上傳
--pG AC 2/161
好笨（
看蘇柏瑄還抓不到 bug，我就跟他說他先去寫 I，他自己 debug 的效益已經太低了，他就同意去寫 I。
我跟鄭忠宜在一旁順過一遍他的 code 之後也找不到問題，就乾脆開始做題。但這裡又有一個大敗筆。
首先我先聽了 E 的題目，發現是白痴煩躁題，等等得寫的那種。後來又不小心看出 C 的最假模擬費用流作法，但我沒發現他是假的，就誤以為我會做，然後打算等等連打這兩題。
等到蘇柏瑄 I 寫完之後
--pI AC 0/201
就輪到我上來從 C 跟 E 選一題，鄭忠宜建議我選比較好 debug 的那題，我第一直覺是想寫 C，但心中又覺得 C 可能會假解，就還是改開始寫 E。
結果 E 寫到一半就發現很多麻煩的地方，頓時有點後悔（但其實我 C 假解的直覺是對的，所以結果論來說又沒錯）。
寫到一半蘇柏瑄就發現他 H 掉什麼 case 了，上來打了一筆果然錯了，馬上改一改
--pH AC 1/245
直覺告訴我這樣在當年就有牌了，但現今的標準絕對不夠。
等到寫完 E 後我範測感覺一直錯很白痴的東西，就果斷把狀況跟隊友說之後丟 code 給他們 debug，我直接開始飆 C。
因為蘇柏瑄沒事做了就一起跟鄭忠宜幫我看 code，看很久之後鄭忠宜就發現我正方形邊界在亂寫，改一改之後還是錯範測只好繼續丟回去給他們。
過一陣子我 C 也寫完了，傳上去
--pC WA
但我完全找不到 bug，因為我的假解超好寫，所以就卡死了（可是我當下還覺得他是對的）。
再過一陣子鄭忠宜就說我 E 忘記驗終點高度也要是對的，我就改好之後成功過了範測，一傳
--pE TLE
這裡有一個問題，就是我們沒有讀到最後要剛好跳到終點，所以我們一直以為是要三分搜跳躍仰角，導致我們其實一直在傳錯的做法，但總之我們就是亂調了一堆東西拿了一堆 WA 跟 TLE 之後悲慘收場。
結語
1. 打這樣還真的有牌，但好爛好爛。
2. ckiseki 金牌太猛了。
3. 後來發現 E 是要剛好跳到終點後就知道可以直接解方程，但不會解，不過馬上就被蛋餅一個透露 1/cos^2 = 1 + tan^2，就會做了 Orz
4. 承上，再把我的 E 改成固定仰角、好好處理三角函數之後就過了...，結果我實作上其實也沒出問題QQ
5. 不過 E 其實在中途我就很抗拒三分搜，我有請鄭忠宜幫我思考能不能不要，但他拒絕我，這感覺欠檢討（Ｘ
6. 蘇柏瑄的狀況則是感覺還沒回穩，希望他這禮拜能調適好Orz
7. C 就是大假解沒話說，但至少看起來我寫得很穩定。
8. 整體感覺我自己的 coding 穩定度是在的，只是會因為太急漏打一些東西，但我有感受到今天自己對實作的信心還不錯，希望這個信心可以保持到正式賽、還可以運氣好能有想清楚的時間再開始寫。
9. 整場感覺幾個挽救點就是 H 不掉 case、C 不假解，當然 G WA 太久可能也是某種可能的影響原因，但真正致命的應該還是前面兩個。
10. D 好像也很簡單但我們完全沒做...其實真的只要不寫出 bug、不假解就贏了吧！？那...那就聽天由命囉XD 願世界給我們一面牌。
11. 最後感謝曾憲揚幫我們兩隊買午餐。
8BQube 加油！
留言
張貼留言