【World Finals 團練紀錄】2016 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/5 13:40~18:40
$\color{green}{A}$ $\color{green}B$ $\color{green}C$ $\color{green}D$ $\color{green}E$ $\color{gray}F$ $\color{green}G$ $\color{gray}H$ $\color{gray}I$ $\color{green}J$ $\color{green}K$ $\color{green}L$ $\color{gray}M$
Penalty：1317 - 21
Rank(versus official)：11
設完環境之後讀題，我翻了一下先打算看 K，看起來像個簡單區間 DP，但計分板上顯示 C 已經被過了，我就先聽蘇柏瑄告訴我題目，然後我再跟他說 K 的題目讓他做完。
其實從 C 開始我的理解題目狀況就偏差，感覺精神狀況欠佳，但又說不出為什麼會有這樣的狀況（
總之多交談一下還是理解了題目，就迅速開掉了。
--pC AC 0/13
再來 E 跟 L 都有人開掉，就請蘇柏瑄去讀 E、我讀 L，我們再互相交流題目。而 L 我看完還沒直接的想法，但 E 就是單純的進位制平方分割經典題，因為我認為蘇柏瑄有 K 的任務我就繼續寫 E、並請蘇柏瑄再轉 L 給鄭忠宜讓他做完。
才一下子就發現 B 也被 benq 開掉了，蘇柏瑄去讀題之後過一陣子就問我「把 n 個數字分成恰 k 組，求每個數字乘上他在的 group 大小的最小總和」怎麼做，第一瞬間我倆都覺得是經典題，但又說不出是什麼，就先放著。
等到我 E 開掉之後。
--pE AC 0/32
就口糊了一下 B 是不是可以換個 dp 狀態做，而不是用原本的 dp[i][j] 表示切到 i 切了 j 段，但蘇柏瑄沒特別說什麼就上去寫了東西，我以為他被我說服了，再加上我有感受到我還沒進入狀況就想說先下機冷靜冷靜。
聽鄭忠宜講 L 的做法之後，知道最後 b-a < 0 的 case 就是死線排程問題，前陣子團練才遇到而已，就在等蘇柏瑄的同時想一下剛剛 claim 的 B，發現我根本在唬爛，趕緊跟蘇柏瑄講
蘇柏瑄：「噢對啊，但我總是要先寫這些，所以不虧。」
好啊（？
總之因為 L 確定了就換我上來寫，上來寫前我就突然覺得原本的 dp 狀態很轉移點單調，表示這可能是 2D/1D 優化，就跟蘇柏瑄說等等他幫我上來寫 dp，晚點直接亂生測資驗單調性。
L 寫完之後一傳
--pL WA
怎麼會是 WA..... 但多想一下就發現剛剛對到死線排程問題的方式對錯了，b 根本才是真正的死線QQ 明明我都知道死線排程問題不是對開始時間排序了，怎麼就還錯這東西啊（
--pL AC 1/57
然後就換蘇柏瑄寫 B 的 dp，我下機看計分板狀況，看起來 G, K 都可以開，就去聽 G。
鄭忠宜說 G 是幾何裸題我一定會，我聽到的第一瞬間就在那邊瞎扯半平面交，然後下一瞬間就發現題目不是要我把全部線段射掉，但 n 只有 2000 所以就是亂做。
蘇柏瑄寫完 B 的 dp 之後我就上來改改 code 驗單調性，只是我一輩子都不記得切 j 段型態的 2D/1D 四邊形怎麼搞，就調了好幾次東西然後又改了一點邊界問題才搞定，確定單調性正確之後剩下改起來就簡單了。
--pB AC 0/82
B 過了之後我當然是繼續火速 G，這種極角排序經典題早就寫膩了，邊寫的途中蘇柏瑄在嚷嚷著 1e10 的 bitset 操作能不能過，但首先空間就快開不下了，他就在努力想怎麼壓空間。
20 分鐘後寫完了 G，抓到鄭忠宜沒看清楚不可以射水平線後，改完檢查一下傳上去
--pG WA
WA...?
一時想不到問題，就讓蘇柏瑄上來寫他的怪 bitset 做法。
抓了十幾分鐘我才發現我 G 窮舉中心後只算了射線，但他可是直線，就趕緊拿電腦過來改，改完傳上去
--pG AC 1/106
到這裡我想步調都還沒有太落後，但接下來就小敗筆了。
因為接下來蘇柏瑄就宣告他的 K 是假解，然後就卡住了，鄭忠宜在旁邊做他的 A，我則是回去幫忙想 K，而蘇柏瑄去讀開始有人做掉、而且明顯就是他的任務的 D。
K 的第一個問題是我沒看清楚範圍就噴了一個區間 dp，導致蘇柏瑄做錯方向；第二個問題是他心中想完一個自己其實也沒很有自信的解後就上去單刷了，這不好。
總之我多想一下就發現 K 用掃描線維護時，想像有個 stack 那就只在意他的 top，所以複雜度就壓一個 n，跟蘇柏瑄講完之後就交給他了，我下機去搞清楚剩下的題目
- pA 鄭忠宜好像搞一陣子了，應該會開掉
- pD 蘇柏瑄寫完 K 之後會繼續寫
- pF 看起來可做，雖然我沒有直接做完，但我覺得蘇柏瑄一定會做
- pH 哇這不是我之前看到的噁心幾何東東嗎，扔了扔了
- pI 看完沒想法，但有一些隊伍開了，應該是認真想就不難的東西
- pJ 看起來是斜率亂搞一通，應該很可開
- pM 好長，丟給鄭忠宜慢慢讀
理想上我們目標應該是 11 題，而因為看起來 A 最多隊過，所以當然是討論 A。
這裡產生了另一個敗筆，就是我去討論 A 的時候完全在狀況外。
我不太清楚是我漏聽還怎樣，總之鄭忠宜早就做完 A 了，但我完全沒發現，所以我就在他跟我講做法的過程中一直在思考怎麼做完，蠻白癡的，然後鄭忠宜也沒發現我在笨，就浪費不少時間在沒意義的討論。
反正過一陣子我才發現他什麼都做完了，我根本不用自己想，好白癡（
蘇柏瑄寫完 K 之後，測了一下就傳
--pK WA
但是點開來的東西是 G 的程式碼，一看發現是我的上傳 script 會在 source 沒副檔名時壞掉（
總之重傳
--pK WA
好慘，不過前面那個 penalty 應該可以選擇性忽視。
K WA 當然就是換我上來寫 A，才寫沒多久蘇柏瑄就發現他會錯的 case，改完再傳
--pK AC 1(+1)/168
姑且算自己 penalty -21（Ｘ
A 寫起來也是很快，所以其實如果早點討論完、甚至我覺得在釐清整場題目前就可以先寫了，有點可惜。
但
--pA WA
怎麼會（
讓蘇柏瑄上去寫 D 之後我就盯著自己的 code，而多看一陣子就發現有地方 j 要加一，範測好爛（
--pA WA
還是 WA！？
又多想了一陣子，才發現我排程的區間根本就在亂取，感覺 A 的交流就整個很失敗，這個鄭忠宜都想好了我還在亂寫（
--pA AC 2/208
接著就是等蘇柏瑄繼續刻 D，我跟鄭忠宜在一旁討論 J，雖然 I 比較多隊過，但 J 對我來說看起來比較可開。
去上個廁所回來我就跟鄭忠宜說可以把他們改成線之後維護上包絡跟下包絡，而鄭忠宜說可能是他在吃毒，但他覺得是用點到凸包切線，我確實覺得自己的做法有點麻煩就聽聽他的，一聽就發現超級對，可是我還沒把點到凸包切線的板子改好，目前只是照抄 ckiseki 的（
但也沒辦法，只能硬著頭皮寫，總之在討論完各種細節後 J 就差不多了，差不多時間蘇柏瑄的 D 也寫完了，但出了點 bug，我就上去先抄各式幾何板子。
途中讓蘇柏瑄改一改之後修好了，他就傳
--pD AC 0/235
他一過我就請他去聽 F，我要全力飆 J。
J 最麻煩的就是 ckiseki 的幾何板子是 complex，跟我們的極不相容，所以我弄了好一陣子，感覺浪費了十多分鐘（
而寫一寫也聽到隊友們看起來覺得 F 做完了，而且應該寫很快，這樣有 10 題，但有點不滿意，我就說雖然我很貪心，但我想要 11 題，讓鄭忠宜去想 I。
這裡我有點搞不清楚怎樣策略才是正確的，11 題感覺是稱職的隊伍該開出來的題數，所以可能該放手一博這樣飆；但保 10 題好像又更重要（
總之還是照著 11 題目標的路線走了，J 火速寫一陣子就快寫完了，最麻煩的是環狀被最少個區間蓋到的點，這個我是直接交給蘇柏瑄思考，畢竟之前也是這樣，他想比較快，剩下因為大多數都是板子所以蠻好寫的，不過寫完一測還是出了點 bug，總之就切一半給蘇柏瑄寫 F。
鄭忠宜抓準時機過來跟我說覺得 simplex 要寫多久，他覺得這只是一個 simplex 笨題，我印象中得抄個十分鐘，所以感覺有點勉強，多問他能不能寫處理好後面的東西後我就繼續 debug 了。
蘇柏瑄 F 寫非常快，但有一個資結要用 pbds 所以他說他先暴力，晚點再給我改。不過範測一測就錯了，他就下去想了一下，我繼續改 J。
改到一半就聽到隊友開始懷疑自己假解了，慘。但總之 J 先修好了。
--pJ AC 0/282
一發是挺開心的，但 F 的噩耗讓我只開心一下下。
總之好像是開不出下一題，問問 I 的狀況鄭忠宜也說他其實還有回溯最短路什麼的，不可能寫完，所以可能就算要保 10 題也壓錯題（
剩下的十幾分鐘我們就在檢討聲之中結束了。
結語
1. 怎麼說，F 的假解可能是意外，感覺最主要的 miss 還是前期步調太慢、然後 K 在假解。
2. 所以我跟蘇柏瑄說之後沒自信的解也要提出來討論。
3. 比對了一下 12 題的銀河戰艦狀況，確實在第五題時我們的狀況都還可以，看得出來是第六題之後出包了，但他們封板後開三題真的鬼。
4. 雖然這場結果不太好，但其實有感覺到我們的問題逐漸在減少了，大概就是心態上的調整，這裡的意思是因為 2014 以前的場很好贏，所以讓我們戒心放鬆了，才會有這次比較悠閒的狀況，我想應該多打幾場就會有感覺。
5. 不過還是有一個問題，為什麼我前期進入狀況的速度這麼慢啊，感覺這不是偶爾的狀況了，原本還以為是寫太少比賽前一天還單刷一場，怎麼沒有改善，可能要多想想原因。
8BQube 加油！
留言
張貼留言